LIFO - Bâtiment IIIA
Rue Léonard de Vinci
F-45067 ORLEANS Cedex 2
Tel: +33 (0)2 38 41 70 11
Fax: +33 (0)2 38 41 71 37
06/03/2017 : A venir
A venir (A venir) Résumé
27/02/2017 : Titre à venir
Martin Delacourt (LIFO, Université d'Orléans) Résumé
13/02/2017 : Small complexity classes for cellular automata, dealing with diamond and round neighborhoods
Anaël Grandjean (LIRMM, Montpellier) Résumé
06/02/2017 : Universality and Computational Completeness of Controlled Leftist Insertion-Deletion Systems
Sergiu Ivanov (TIMC-IMAG, Grenoble) Résumé
16/01/2017 : On the coinductive nature of centralizers
Charles Grellois (Università di Bologna) Résumé
Titre à venir Martin Delacourt, LIFO, Université d'Orléans
Résumé à venir.
Small complexity classes for cellular automata, dealing with diamond and round neighborhoods Anaël Grandjean, LIRMM, Montpellier
We are interested in 2-dimensional cellular automata and more precisely in the recognition of langages in small time. The time complexity we consider is called real-time and is rather classic for the study of cellular automata. It consists of the smallest amount of time needed to read the whole imput. It has been shown that this set of langages depend on the neighborhood of the automaton. For example the two most used neighborhoods (Moore and von Neumann ones) are different with respect to this complexity. Our study deals with more generic sets of neighborhoods, round and diamond neighborhoods. We prove that all diamond neighborhoods can recognize the same langages in real time and that the round neighborhoods can recognize stricly less than the diamond ones.
Universality and Computational Completeness of Controlled Leftist Insertion-Deletion Systems Sergiu Ivanov , TIMC-IMAG, Grenoble
In this work, we consider leftist insertion-deletion systems (LIDS), in which all rules have contexts on the same (left) side, and may only insert or delete one symbol at a time. We start by introducing extended rules, in which the contexts may be specified as regular expressions, instead of fixed words. We prove that, in this case, computational completeness is achieved when additional control mechanisms are used (graph control with two states, matrix control with binary matrices and random-context control). We then show how rules with regular contexts can be simulated by conventional rules checking one-symbol (resp. two-symbol) left contexts for insertion and two-symbol (resp. one-symbol) left contexts for deletion. This simulation does not generally hold in the controlled case, however. Hence, we provide a construction simulating an arbitrary 2-tag system using extended rules and which can be rewritten in terms of conventional rules of types above. These constructions imply that the studied insertion-deletion systems are universal.
On the coinductive nature of centralizers Charles Grellois, Università di Bologna
The centralizer of a language L is defined as the largest solution C(L) to the language equation XL = LX. In other terms, any word u.v obtained as a concatenation of a word u of L and of a word v of C(L) should admit a factorization starting by a word of C(L) and ending with a word of L. We can understand this as a rewriting process on the words of C(L). Kunc designed in 2006 a regular language L in which this rewriting process is such that it simulates the transitions of a Minsky machine. However, he could deduce from this that C(L) is not recursively enumerable... We will sketch a variant of his proof using Turing machines, and introduce the key concept of coinduction, which solves the mystery of Kunc's result: centralizers' behaviour is dual to the one of machines.