18/10/2010 : à venir
Eric Kow (Natural Language Technology Group, University of Brighton, Royaume-Uni) Résumé

13/09/2010 : à venir
Martin Matamala (Université du Chili) Résumé

05/07/2010 : Étude de la terminaison des systèmes de réécriture de termes linéaires bounded.
Marc Sylvestre (LABRI (Bordeaux)) Résumé

28/06/2010 : On the Computational Complexity of Dominance Links in Grammatical Formalisms
Sylvain Schmitz (laboratoire LSV / ENS de Cachan) Résumé

07/06/2010 : Algorithmes exacts et exponentiels : colorations de graphes
Jean-François Couturier (LITA, Université Paul Verlaine - Metz) Résumé

17/05/2010 : Multi-view Learning for Text Subjectivity Classification
gael dias (HULTIG - Université de Beira Interior, Portugal) Résumé

10/05/2010 : Attack–Defense Trees
Barbara Kordy (Université du Luxembourg ) Résumé

15/03/2010 : Le traitement des alias internes dans l'outil de génération de tests PathCrawler
Nikolai Kosmatov (LSL - CEA LIST) Résumé

22/02/2010 : Communication Complexity and Intrinsic Universality in Cellular Automata
Ivan Rapaport (Université du Chili (Santiago, Chili)) Résumé

22/02/2010 : Séminaire "obligatoire": Rapport d'activité 2010
Jerome Durand-Lose (LIFO) Résumé
Attention : 15H

08/02/2010 : Décompositions et logique monadique
Michaël Rao (Michaël Rao (LaBRI, Bordeaux) ) Résumé

01/02/2010 : OPA -- Parés à reconquérir le web
David Teller (ML-state) Résumé

01/02/2010 : Cyclic partitions of complete uniform hypergraphs
Pawel Wojda (Cracovie) Résumé
Attention : 15 H

25/01/2010 : Qu'est-ce que la complexité linguistique ?
Philippe Blache (Laboratoire Parole et Langage, Université de Provence, Aix) Résumé

18/01/2010 : Annoter de des textes tu sais tu te demandes la syntaxe elle est comment hein
Sylvain Kahane (Modyco, Université Paris Ouest Nanterre) Résumé

18/01/2010 : GigaVoxels: Parallélisme au coeur du rendu haute performance
Cyril Crassin (NRIA Rhones-Alpes, équipe ARTISS) Résumé
Attention : 10H30

Résumés des séminaires

à venir Eric Kow, Natural Language Technology Group, University of Brighton, Royaume-Uni
à venir

à venir Martin Matamala, Université du Chili
à venir

Étude de la terminaison des systèmes de réécriture de termes linéaires bounded. Marc Sylvestre, LABRI (Bordeaux)
Résumé : Pour chaque entier k, on définit une nouvelle notion de réécriture pour la classe des systèmes de réécriture de termes linéaires: la réécriture k-bounded. La réécriture k-bounded est une restriction de la notion classique de réécriture. On montre que différents problèmes de terminaison pour la réécriture k-bounded sont décidables (terminaison uniforme k-bounded, terminaison inverse uniforme k-bounded, terminaison k-bounded, et terminaison inverse k-bounded). La classe des systèmes k-bounded (BO(k)) est, par définition, l'ensemble des systèmes linéaires pour lesquels toute dérivation peut être remplacée par une dérivation k-bounded. En général, pour les systèmes BO(k), le problème de la terminaison uniforme (resp. terminaison inverse uniforme) n'est pas équivalent au problème de la terminaison uniforme k-bounded (resp. inverse terminaison uniforme k-bounded), et le problème de la terminaison (resp. terminaison inverse) n'est pas équivalent au problème de la terminaison k-bounded (resp. terminaison inverse k-bounded). Toutefois, pour les systèmes BO(k) tels que toute dérivation peut être remplacée par une dérivation BO(k) de même longueur, ces problèmes sont équivalents. La classe des systèmes qui respectent cette dernière propriété est notée BOLP(k). La classe BOLP, union des classes BOLP(k), contient (strictement) de nombreux systèmes étudiés auparavant: les systèmes de réécriture de mots qui sont l'inverse de systèmes basiques à gauche, les systèmes de réécriture de termes linéaires growing, et les systèmes de réécriture linéaires qui sont l'inverse de systèmes appellés finite-Path-Overlapping systems

On the Computational Complexity of Dominance Links in Grammatical Formalisms Sylvain Schmitz, laboratoire LSV / ENS de Cachan
Dominance links were introduced in grammars to model long distance scrambling phenomena, motivating the de?nition of multiset-valued linear indexed grammars (MLIGs) by Rambow (1994b), and inspiring quite a few recent formalisms. It turns out that MLIGs have since been rediscovered and reused in a variety of contexts, and that the complexity of their emptiness problem has become the key to several open questions in computer science. We survey complexity results and open issues on MLIGs and related formalisms, and provide new complexity bounds for some linguistically motivated restrictions.

Algorithmes exacts et exponentiels : colorations de graphes Jean-François Couturier , LITA, Université Paul Verlaine - Metz
Nous présenterons des algorithmes exacts dont le temps d'exécution est exponentiel au rapport de la taille de l'entrée afin de résoudre des problèmes NP-complets. En particulier, nous étudierons des problèmes de coloration de graphes. Nous discuterons brièvement différentes colorations possibles puis nous présenterons un algorithme pour resoudre le probleme L(2,1)-labeling. Finalement, nous discuterons de l'analyse du temps d'exécution de cet algorithme. Ce travail est une collaboration avec D. Kratsch et P. Golovach.

Multi-view Learning for Text Subjectivity Classification gael dias, HULTIG - Université de Beira Interior, Portugal
In this paper we consider the problem of building models that have high sentiment classification accuracy across domains. For that purpose, we present and evaluate a method based on co-training using both high-level and low-level features. In particular, we show that multi-view learning combining high-level and low-level features with adapted classifiers can lead to improved results over text subjectivity classification. Our experimental results present accuracy levels across domains of 86.4% combining LDA learning models over high-level features and SVM over bigrams.

Attack–Defense Trees Barbara Kordy, Université du Luxembourg
Security assessment of complex systems is a standard but suboptimal pro- cedure due to its informal nature. While a formal approach would be desirable, but out of reach, a systematic approach would be beneficial and feasible. At- tack trees, introduced by Schneier and formalized by Mauw and Ooostdijk, are a well–known methodology to describe the possible security weaknesses of a system. An attack tree basically consists of a description of an attacker’s goals and their refinement into sub-goals. In order to provide an excellent systematic and practical security assessment methodology we extend attack trees with defense nodes. These nodes allow us to represent countermeasures that a defender can employ to prevent given attack components. Therefore, we define attack–defense trees (ADT) where nodes of both types — attack or defense — may appear at any level of the tree. In this work, we provide a formal basis for attack–defense trees. We present their syntax and discuss possible semantics. We also investigate interesting properties of ADTs, and show how to analyze an attack/defense scenario by using attributes.

Le traitement des alias internes dans l'outil de génération de tests PathCrawler Nikolai Kosmatov, LSL - CEA LIST
Nous présentons le problème des alias dans le cadre de la méthode de génération automatique de tests tous-les-chemins par la recherche en profondeur d'abord à l'aide de l'exécution symbolique en contraintes. Nous classons les alias en deux classes : les alias externes présents au point d'entrée dans la fonction sous test (à cause des pointeurs dans les entrées de la fonction) et les alias internes créés lors de l'exécution symbolique. Nous proposons une extension originale de la méthode de génération pour les programmes C avec des alias internes. Elle limite l'énumération des valeurs d'entrée et la génération de cas de test superflus. Les premières expériences montrent que cette méthode peut considérablement améliorer les performances des outils existants sur les programmes avec des alias. Nous montrons également que la génération de test pour le critère tous-les-chemins est en général NP-difficile en présence des alias, et définissons une classe plus restrictive de programmes pour lesquels cette génération devient polynomial.

Communication Complexity and Intrinsic Universality in Cellular Automata Ivan Rapaport, Université du Chili (Santiago, Chili)
The notions of universality and completeness are central in the theories of computation and computational complexity. However, proving lower bounds and necessary conditions remains hard in most of the cases. In this talk we introduce necessary conditions for a cellular automaton to be ``universal'', according to a precise notion of simulation, related both to the dynamics of cellular automata and to their computational power. This notion of simulation relies on simple operations of space-time rescaling and it is intrinsic to the model of cellular automata. Intrinsinc universality, the derived notion, is stronger than Turing universality, but more uniform, and easier to define and study. Our approach builds upon the notion of communication complexity, which was primarily designed to study parallel programs, and thus it is, as we show in this article, particulary well suited to the study of cellular automata: it allows to show, by studying natural problems on the dynamics of cellular automata, that several classes of cellular automata, as well as many natural (elementary) examples, can not be intrinsically universal.

Séminaire "obligatoire": Rapport d'activité 2010 Jerome Durand-Lose, LIFO
Tout ce que vous avez toujours voulu savoir sur l'organisation de ce travail au niveau des équipes et des individus.

Décompositions et logique monadique Michaël Rao, Michaël Rao (LaBRI, Bordeaux)
Les décompositions jouent un rôle important en algorithmique et en théorie des graphes. Un exemple bien connu est la largeur arborescente utilisée dans la série de papiers sur les mineurs de graphes de Robertson et Seymour. Je ferai un tour d'horizon des différents résultats connus sur la clique-width de Courcelle, qui peut être vu comme une généralisation de la décomposition arborescente (notamment l'idée de la preuve de Courcelle et al. sur l'existence d'un algorithme linéaire pour tout problème exprimable en logique monadique du second ordre sur les graphes de clique width borné), ainsi que les récentes avancées dues à la largeur de rang (rank-width) de Seymour et Oum. Je présenterai également quelques questions ouvertes du domaine.

OPA -- Parés à reconquérir le web David Teller, ML-state
Le web nous a tous changé la vie, à coups de Wikipedia, de forums de Google Maps, et de centaines d'autres sites et applications riches, puissantes et accessibles depuis partout. Le web change la vie de pas mal de monde, à coups d'injections SQL, d'injections XSS, de pages laissées publiques par erreur sur des sites autrement sécurisés, et de centaines d'autres failles de sécurité de haut et bas niveau, exploitées ou qui attendent de l'être. Forcément, c'est moins chouette. À qui la faute ? Peut-être tout simplement à la montagne de technologies distinctes que doit maîtriser le développeur pour écrire la moindre application. Six ou sept langages dans le meilleur des cas, facilement des dizaines dès que les choses se compliquent, et autant de technologies à configurer individuellement, autant de connexions à écrire à la main et en espérant ne pas se tromper, souvent à l'aveuglette et sans sémantique claire. Dans ces conditions, impossible de vérifier quoi que ce soit. À l'heure actuelle, le web est perdu sous PHP, SOAP, AJAX, JSON, le non-typé, le code eval()-ué ou généré dynamiquement à coups de chaînes de caractères. Mais tout n'est pas perdu. Venue d'un obscur pays d'Europe où l'on mange du fromage à pâte crue et où l'on croit à la sémantique et aux systèmes de types, une nouvelle technologie se lance à l'assaut du web. OPA : One Pot Application. Un nouveau langage de programmation pour le web, de haut niveau, avec une sémantique simple et claire. Avec OPA, une application entière s'écrit à l'aide d'un seul langage, qui est compilé de manière transparente vers la multitude de technologies nécessaires pour faire tourner le web. Pas d'injections SQL, pas d'injections XSS, pas de pages laissées publiques par accident, et du code clair et qui permet aux développeurs de se concentrer sur les questions de haut niveau. Ah, et puis des preuves en Coq. Parés à reconquérir le web ?

Cyclic partitions of complete uniform hypergraphs Pawel Wojda, Cracovie
By $\K$ we denote the complete $k$-uniform hypergraph of order $n$, $1\le k \le n-1$, i.e. the hypergraph with the set $V_n=\{ 1,2,...,n\}$ of vertices and the set $V_n \choose k$ of edges. If there exists a permutation $\sigma$ of the set $V_n$ such that $\{ E,\sigma (E),..., \sigma^{p-1}(E) \}$ is a partition of the set $V_n \choose k$ then we call it $p$-cyclic partition of $\K$ and $\sigma$ a permutation of $p$-cyclic partition of $\K$. If $p=2$ we have $\sigma (E)={V_n \choose 2}-E$ and the hypergraph $(V_n;E)$, and $(V_n;\sigma (E))$ as well, is self-complementary $k$-uniform hypergraph.\\ We shall give several necessary and sufficient conditions for a permutation to be a permutation of $p$-cyclic partition of $\K$.\\ It is true that that if $n \choose k$ is even then there is a $k$-uniform self-complementary hypergraph of order $n$. The corresponding result is no longer true for $p$-cyclic partitions of $\K$, that is there are such $p,k$ and $n$ that $n \choose k$ is divisible by $p$, but there is no $p$-cyclic partition of $\K$. We shell discuss the problem for which $p, k$ and $n$ there is a $p$-cyclic partition of $\K$? The problem of $p$-cyclic partitions of the complete hypergraph $(V_n;2^{V_n}-\{ V_n, \emptyset \})$ will be also discussed and solved.

Qu'est-ce que la complexité linguistique ? Philippe Blache, Laboratoire Parole et Langage, Université de Provence, Aix
La notion de complexité est importante en linguistique : existe-t-il des constructions ou des phénomènes linguistiques plus complexes que d'autres à traiter ? Si oui, quels sont les facteurs de cette complexité, comment les identifier et finalement, comment les utiliser ? Il convient tout d'abord de préciser ce que recouvre cette notion de complexité. Du point de vue algorithmique, chacun voit de quoi il s'agit. Mais cela ne recouvre que très partiellement le problème dès lors qu'on aborde la question du point de vue cognitif. La littérature est en effet abondante sur ce sujet, mais seulement dans le domaine de la psycholinguistique, et notamment dans la perspective de la description des phénomènes de "processing". Je propose tout d'abord dans cette présentation un panorama de la question, et qui nous permettra d'identifier les phénomènes habituellement considérés comme facteur de complexité. La question fondamentale qui est alors posée est celle de l'identification, la quantification, voire l'évaluation de cette complexité. Il s'agit pour cela de proposer tout d'abord un cadre méthodologique permettant d'identifier et décrire ces phénomènes. La plupart des approches sont très dépendantes de la représentation formelle de la structure syntaxique. C'est inévitable dès lors qu'on décrit des phénomènes syntaxiques. Mais dans quelle mesure cela peut-il constituer un biais ? Je présenterai quelques pistes de réflexion permettant de proposer une approche basée sur les contraintes comme bonne candidate au traitement de ce problème.

Annoter de des textes tu sais tu te demandes la syntaxe elle est comment hein Sylvain Kahane, Modyco, Université Paris Ouest Nanterre
Nous nous intéresserons à l'annotation syntaxique de corpus de français parlé. Ce travail est mené dans le cadre du projet ANR Rhapsodie dirigé par Anne Lacheret et visant à constituer un corpus annoté en syntaxe et en prosodie. Nous nous intéresserons tout particulièrement à tous les phénomènes qui échappent à une annotation classique de type dépendance ou constituance et dont une partie constituent ce qu'on appelle la macro-syntaxe : disfluence, reformulation, effet deux-points, question-réponse, insertion, détachement, greffe, etc. Nous discuterons à la fois les phénomènes observés, leur annotation syntaxique, la stratégie d'annotation et les outils développés.

GigaVoxels: Parallélisme au coeur du rendu haute performance Cyril Crassin, NRIA Rhones-Alpes, équipe ARTISS
Le domaine de l'informatique graphique et en particulier du rendu temps-réel est en train de vivre une véritable mutation de par l'évolution des processeurs graphiques (GPU) vers des architectures parallèles de plus en plus génériques et totalement programmables. Cette évolution s'accompagne d'une évolution des méthodes de programmation de ce type d'architectures avec de nouveaux langages parallèles tels que CUDA ou OpenCL. Ceci entraine une mutation des problématiques de rendu qui sont de plus en plus proches de problèmes de parallélisme pur. Cyril Crassin est doctorant dans l'équipe ARTIS de l'INRIA Rhone-Alpes, équipe spécialisée en informatique graphique. Cyril présentera ses travaux de thèse à la croisée du rendu haute performance et du parallélisme. Il présentera en particulier GigaVoxels, un nouveau pipeline de rendu permettant le rendu interactif de très grosses masses de voxels. Ce pipeline est entièrement développé en CUDA et tire au maximum parti de l'architecture data-parallel des GPU modernes. Il se compose d'une structure d'accélération hiérarchique, d'un mécanisme de gestion de données "out-of-core" et d'un système de rendu de voxels par ray-tracing. Plus d'infos ici: http://artis.imag.fr/Membres/Cyril.Crassin/