m

F Nous contacter

0

Documents  Diekert, Volker | enregistrements trouvés : 2

O
     

-A +A

P Q

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Computer Science

The talk is based on a joint work with Kufleitner, Reinhardt, and Walter. The result was presented first at ICALP 2012 in Warwick. It shows that for each recognizable language L there exist some finite confluent and length-reducing semi-Thue system S such that L is a finite union of congruence classes with respect to S. This settled a long standing conjecture in formal language theory which dates back to a JACM publication by McNaughton, Narendran and Otto in 1988. Substantial steps towards the solution were done by Reinhardt and Therien concerning group languages and in 2011 in a joint work of the speaker with Kufleitner and Weil for aperiodic languages. The solution for the aperiodic languages and the general case became possible by proving in each of these cases a much stronger result, thereby "loading the induction". The talk is based on a joint work with Kufleitner, Reinhardt, and Walter. The result was presented first at ICALP 2012 in Warwick. It shows that for each recognizable language L there exist some finite confluent and length-reducing semi-Thue system S such that L is a finite union of congruence classes with respect to S. This settled a long standing conjecture in formal language theory which dates back to a JACM publication by McNaughton, ...

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 164 p.
ISBN 978-3-540-53031-2

Lecture notes in computer science , 0454

Localisation : Collection 1er étage

algorithmique de graphe # combinatoire # générateur # informatique théorique # mode de calcul # problème de mots # relation # réécriture des systèmes # semi-groupe libre # théorie des graphes

05C85 ; 20M05 ; 68Q10 ; 68Q42 ; 68R15

... Lire [+]

Z