Lifo - Laboratoire d'Informatique Fondamentale d'orléans INSA Centre Val de Loire Université d'Orléans Université d'Orléans

Lifo > Les séminaires du LIFO

 English Version



Contact

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



Les séminaires du LIFO


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

Sauf exception, les séminaires se déroulent le lundi de 14h à 15h, Salle de réunion 1, bâtiment IIIA (voir plan du campus).


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é


Résumés des séminaires


A venir A venir, A venir


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.