Je définis une largeur de graphes strictement intermédiaire entre "pathwidth" et "treewidth". Cette définition est motivée par la construction d'automates pour vérifier les propriétés MSO avec quantifications d'arêtes. Elle se définit par des restrictions sur des opérations qui définissent la clique-width. Je ferai la comparaison avec d'autres variantes de la clique-width.
The talk is about a generalization of various results on the decidability of emptiness for several restricted classes of sequential and distributed automata with auxiliary storage (stacks, queues) that have recently been proved. Our generalization relies on reducing emptiness of these automata to finite-state *graph automata* (without storage) defined on monadic second-order (MSO) definable graphs of bounded tree-width, where the graph structure encodes the mechanism provided by the auxiliary storage. Our results outline a uniform mechanism to derive emptiness algorithms for automata, explaining and simplifying several existing results, as well as proving new decidability theorems.
We study three algorithmic problems for probabilistic automata on finite words: the Emptiness Problem, the Isolation Problem and the Value 1 Problem.
The Emptiness Problem asks, given some probability 0<=\lambda<= 1, whether there exists a word accepted with probability greater than \lambda, and the Isolation Problem asks whether there exist words whose acceptance probability is arbitrarily close to \lambda. Both these problems are known to be undecidable.
About the Emptiness problem, we provide a new simple undecidability proof. The Value 1 Problem is the special case of the Isolation Problem when \lambda=1 or \lambda=0. The decidability of the Value 1 Problem was an open question. We show that the Value 1 Problem is undecidable. Moreover, we introduce a new class of probabilistic automata, #-acyclic automata, for which the Value 1 Problem is decidable.
Many important problems are NP-complete, and yet for practical reasons we must strive to cope algorithmically with them. Already in the 90s, Downey and Fellows proposed to introduce a second dimension called parameter to complexity analysis for a refined notion of efficiency in terms of complexity class FPT (Fixed Parameter Tractability). Among other approaches, the theory can benefit from a graph decomposition point of view: first divide the input into pieces, then define the parameter by measuring the worst piece. Nowadays, tree-width and tree-width decompositions are very useful in this perspective because many NP-complete problems become tractable on graphs of small tree-width.
In this talk we review the algorithmic success of tree-width and discuss how to extend this to decompositions more powerful than tree-width, in terms of allowing to decompose more graphs. We address classical decomposition frameworks related to clique-width and NLC-width, as well as new frameworks related to rank-width, module-width, and the newly introduced boolean-width.
Many learning algorithms have been proposed for diverse classes of formal languages under various learning schemes. In particular the literature has achieved successful results on learning regular languages. Yet many contemporary applications involve context-free structures or even more complex structures. Learning context-free and mildly context-sensitive languages from positive examples is a topical and challenging task in grammatical inference. Recently Clark and others have proposed learning algorithms for special kind of context-free languages based on an algebraic approach, where the target languages are defined by their algebraic property rather than a grammatical characterization. This talk presents how such a new approach enables us to learn richer classes of languages, particularly mildly context-sensitive languages.
The hierarchy of collapsible pushdown graphs is an extension of the hierarchy of higher-order pushdown graphs. Higher-order pushdown graphs are closely related to the Caucal-Hierarchy and inherit from this connection the decidability of the monadic second order model checking. Collapsible pushdown graphs instead do no have decidable monadic second-order theories. But they still enjoy decidable modal mu-calculus model checking. If they have decidable first-order theories is an open problem. We make a first step towards a solution to this problem by showing that all graphs in the second level of the hierarchy are tree-automatic and thus have decidable first-order theories.
MIX is the language built on {a;b;c} that contains the words that have the same number of a's, b's and c's. This language is of particular importance for the definition of mildly context sensitive languages in computational linguistics proposed by Joshi which is supposed to capture the class of human languages and which roughly coincides with Multiple Context Free Languages (MCFLs). Joshi has indeed tried to exclude MIX from this class and since Joshi's proposal in the early 80's the problem of whether MIX is an MCFL is open. This problem has another interest in group languages because it is rationally equivalent to the language O2 built on {a;a_;b;b_} which contains the words having the same number of a's and a_'s and the same number of b's and b_'s. O2 is a word language for the group Z² and proving that MIX is a 2-MCFL is equivalent to prove that O2 is a language defined by a third order pushdown automaton. So in this talk we give a proof that O2 is a 2-MCFLs (which therefore implies that MIX is a 2-MCFL). This result shows that mildly context sensitive languages may need to be redefined, and it also exhibits the first, to our knowledge, group language which is not virtually free (or equivalently defined by a context free grammar) and that is definable by means of higher order pushdown automata. The proof we propose mostly relies on a geometric theorem about Jordan curves which involves some basic algebraic topology.
The theory of varieties, which describes a correspondence between certain classes of recognizable languages and certain classes of finite monoids, provides a solid framework for the classification of recognizable languages and for many important decidability algorithms. It was first formulated in the mid-1970s and has evolved substantially since. However, recent work by Gehrke, Grigorieff, Pin and Straubing has brought to light a completely new approach of this theory. The role of topology and of the free profinite monoid was already known (its elements are used in identities to describe varieties of finite monoids, Reiterman's theorem) but in this new approach, the topological angle is given the first place. The notion of profinite identity can be relaxed (to a notion called profinite equation), and it can now be interpreted to describe a class of languages rather than a class of finite monoids. There results a classification theorem which generalizes Eilenberg's theorem, in the sense that it applies to families of languages with many less closure properties than varieties: in fact, they only need to be closed under finite unions and intersections. This is the case for instance of the class of languages that are definable in any "reasonable" fragment of logic (closed under conjunction and disjunction).
I will present the main features of this new approach to variety theory and I will give a few examples of applications (to families of languages that are far from being varieties).
Dans un jeu à somme nulle, deux joueurs s'affrontent en ayant des intérêts complètement opposés: les gains du premier joueur sont égaux aux pertes du second joueur.
Un jeu à somme nulle est "déterminé" si il possède une certaine valeur v, c'est-à-dire si, informellement, le premier joueur a une stratégie qui lui garantit de gagner au moins v et le second joueur a une stratégie qui lui garantit de perdre au plus v.
Martin a prouvé la détermination de deux classes de jeux très générales: les jeux à somme nulle et à information parfaite (en 1975) et les jeux de Blackwell (en 1998). Les hypothèses de ces deux théorèmes sont très faibles: il suffit que la fonction de paiement soit Borel-mesurable.
Dans cet exposé, on présentera des esquisses de preuve de ces deux théorèmes fascinants.
Les matroïdes sont des objets généralisant la notion d'indépendance linéaire. Les graphes peuvent être vus par exemple comme des matroïdes très simples. Dans cet exposé on montre comment les idées de décomposition de graphe (tree-width, branch-width) peuvent être adaptées aux matroïdes. Pour ces matroïdes la décision de la logique monadique du second ordre est facile. On montre ensuite comment on peut construire des classes de matroides représentés par des arbres, afin que la logique monadique du second ordre soit également décidable en temps linéaire.
Dans les jeux d'exploration des graphes, une équipe de gendarmes cherche à attraper un voleur rapide. L'intérêt de ces jeux est que le nombre minimal de gendarmes nécessaire pour capturer le voleur correspond, selon les variantes (voleur visible, invisible...), à des paramètres connus des graphes (largeur arborescente, de chemins...).
Pour chaque variante, on peut définir des stratégies particulières pour les gendarmes sous la forme de décompositions et pour le voleur sous la forme d'enchevêtrements. Décompositions et enchevêtrement s'excluent mais certaines variantes admettent un théorème min/max du type:« il existe une décomposition si et seulement si il n'existe pas d'enchevêtrements ». Jusqu'à présent, chaque variante de ces théorèmes min/max nécessitait une preuve ad-hoc. Je vais présenter un travail dans lequel je prouve un unique théorème min/max pour un méta-jeu qui généralise toutes les variantes connues à ce jour.
While the general isomorphism problem of automatic structures is known to be highly undecidable (more precisely: complete for the first level of the arithmetical hierarchy and therefore as complicated as possible), it was shown decidable for certain classes (e.g., ordinals or Boolean algebras). The talk investigates this problem for automatic equivalence structures, trees of bounded height, trees of finite height, and linear orders. It presents results that were obtained in joint work with Markus Lohrey and Jiamy Liu (Leipzig).
La propriété de Focalisation est un résultat essentiel de la théorie de la démonstration de la logique linéaire qui met en évidence le rôle essentiel de la polarité en logique. La Focalisation a permis des avancées importantes, allant de la programmation logique linéaire aux sémantiques de jeux.
La ludique, quant à elle, est un formalisme logique introduit par Girard il y a une dizaine d'années dont l'élément de base est la notion d'interaction et que Terui a revisité il y a un an en apportant de nouvelles perspectives. Dans cet exposé qui est le résultat d'une collaboration avec Basaldella et Terui, je présenterai une analyse interactive de la propriété de focalisation menée dans le cadre de la Ludique.
J'expliquerai également les motivations initiales de ce travail provenant de la remarque que la propriété de focalisation peut être vue comme reliée à des résultats de théorie de la complexité.
En 1972, Françoise Dejean a conjecturé que le plus grand exposant inévitable d'une répétition dans un mot infini sur k lettres (k>=2) est k/(k-1), sauf pour k=3 pour lequel il est 7/4, et pour k=4 pour lequel il est 7/5. Ceci généralise le résultat de Thue (1906) montrant que la séquence de Thue-Morse évite toutes les répétitions d'exposants strictement plus grands que 2 (c-à-d les facteurs du type "uux", où "x" est la première lettre du mot "u"). Cette conjecture a successivement été montrée pour k=3 par Dejean (1972), k=4 par Pansiot (1984), 5<=k<=11 par Moulin Ollangier (1992), k>=33 par Carpi (2007), 12<=k<=14 par Mohammad-Noori et Currie (2007), et k>=27 par Currie et Rampersad (2009). Je présente une généralisation de la méthode de Moulin Ollagnier sur certains cas de HDOLs, qui permet de montrer la conjecture dans les cas 8<=k<=38. Cette méthode est également utilisée pour montrer certains cas d'une conjecture plus forte de Pascal Ochem.
First-order logic is known to have limited expressive power over finite structures. It enjoys in particular the locality property, which states that first-order formulae cannot have a global view of a structure. This limitation ensures on their low sequential computational complexity. We show that the locality impacts as well on their distributed computational complexity. We use first-order formulae to describe the properties of finite connected graphs, which are the topology of communication networks, on which the first-order formulae are also evaluated. We show that over bounded degree networks and planar networks, first-order properties can be frugally evaluated, that is, with only a bounded number of messages, of size logarithmic in the number of nodes, sent over each link. Moreover, we show that the result carries over for the extension of first-order logic with unary counting.
We give a reduction of the boundedness problem for monadic second-order logic over trees to the limitedness problem for distance automata. As a consequence, we obtain the decidability of the boundedness problem for MSO over classes of structures of bounded tree width.
In this talk we present higher order multi-stack pushdown systems (hmpds). We show that parity games over bounded phase hmpds are effectively solvable and winning strategy in these games can be effectively synthesized.
The proof is by reducing the parity games over bounded phase hmpds to finite state parity games. We shall describe this reduction in some detail.