- Renseignements pratiques
- Enseignement

**LIFO** - Bâtiment IIIA

Rue Léonard de Vinci

B.P. 6759

F-45067 ORLEANS Cedex 2

**Email:**
contact.lifo

**Tel:** +33 (0)2 38 41 70 11

**Fax:** +33 (0)2 38 41 71 37

Accès par année : 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017

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.

Université d'Orléans | INSA Centre Val de Loire