• Membres RA

• accueil pôle MDSC

Contributors : Jean-Marc Fédou, Sandrine Julia, Sylvain Lippi, Igor Litovsky

This research deals with formal languages and automata theory. We consider rational languages of infinite words which are recognized by Büchi and Muller automata. An ω-language can be obtained from a classical formal language by the application to its words of the operation of infinite concatenation denoted .^ω. We explore the remaining open problems about the set of all the languages generating the same ω-language. Codes represent the most well-known languages because decoding any word into words in the code is unique. The challenging problem we focus on is the question of deciding whether a rational ω-language is generated by a code.

Since 1994, the codes admit a characterization in terms of infinite words. We derive from this result the definition of a new class of languages, the reduced languages. A code is a reduced language but the converse does not hold. The idea is to “reduce” easy-to-obtain minimal ω-generators in order to obtain codes among the set of ω-generators [IC-48].

The ambiguous words in L⁺ prevent the language L from being a code. Respectively, the ambiguous infinite words in L^ω prevent a language L from being an ω-code. We extensively study these two sets in order to clarify their structures and also their links. In addition, we propose a restricted notion of ambiguity, the strong ambiguity coupled to its infinitary version. The aim is to refine the descriptions previously obtained. Indeed, finding appropriate representatives constitutes a challenge to go deeper inside open decidability problems like deciding whether a rational ω-language is generated by a code or an ω-code [NC-8].

Consider now a rational language L. How to decide whether L^ω is generated by an ω-code ? We investigated languages whose ambiguity and/or !-ambiguity are minimal. We introduced the notion of family over relations fulfilled by words. If L is finite, the number of families is also finite. Each of them produces its proper set of incompatible prefixes. In case of a unique family, this leads to two twin languages that are candidates to be ω-generators and ω-codes if any exists [CwP-6].

We also followed a more logic & computability oriented research direction, studying hard interaction systems: a byproduct of proof nets in linear logic which is also a model of computation like Turing Machines, lambda-calculus or cellular automata. One of the main questions asked by the community was "is there a universal system that can simulate all the others?" like a universal Turing machine can simulate all other Turing machines? Two different universal hard systems have been proposed [IC-10, IC-11] based on different strategies. We have also proposed in [IJ-35] a more comprehensive study that exhibits some classes of universal systems in a broader context.

In 2009, we have obtained a first CNRS cooperation with the Academy of Sciences of Hanoi, Vietnam. The goal was to reinforce an old and informal collaboration, renewed by the venue in Nice of a PhD-student from Hanoi. Prof. Do Long Van from Hanoi, I. Litovsky and S. Julia were able to work together with the PhD. student. The continuation of this cooperation will be asked by september 2010, including new people from both sides.