On One-Rule Grid Semi-Thue Systems

Résumé : La famille des systèmes de semi-Thue à une seule règle "en grille", introduite par Alfons Geser, est la famille des systèmes de réécriture de mots pour lesquels il existe une lettre apparaissant autant de fois dans la partie gauche et dans la partie droite de leur unique règle. Nous prouvons que, pour tout système S de cette famille, l'ensemble S(w) des mots obtenus à partir du mot w en appliquant itérativement la règle de réécriture de S est un langage algébrique constructible. Nous prouvons également que l'ensemble Loop(S) des mots qui sont à l'origine d'une boucle de réécriture pour un systèmes de semi-Thue à une seule règle "en grille" S est un langage régulier.
Type de document :
Article dans une revue
Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2012, Words, Graphs, Automata and Languages. Special Issue Honoring the 60th Birthday of Professor Tero Harju, 116 (1-4), pp.189-204. <10.3233/FI-2012-678>


https://hal.inria.fr/hal-00749289
Contributeur : Yves Roos <>
Soumis le : mercredi 7 novembre 2012 - 11:12:31
Dernière modification le : samedi 27 juin 2015 - 01:07:02
Document(s) archivé(s) le : vendredi 8 février 2013 - 03:42:50

Fichier

on-one-rule-grid-semi-thue-sys...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Michel Latteux, Yves Roos. On One-Rule Grid Semi-Thue Systems. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2012, Words, Graphs, Automata and Languages. Special Issue Honoring the 60th Birthday of Professor Tero Harju, 116 (1-4), pp.189-204. <10.3233/FI-2012-678>. <hal-00749289>

Exporter

Partager

Métriques

Consultations de
la notice

217

Téléchargements du document

186