On One-Rule Grid Semi-Thue Systems

Latteux, Michel; Roos, Yves

Document type :

Compte-rendu et recension critique d'ouvrage

DOI :

10.3233/FI-2012-678

Title :

On One-Rule Grid Semi-Thue Systems

Author(s) :

Latteux, Michel [Auteur]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Roos, Yves [Auteur]

Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Modeling Tree Structures, Machine Learning, and Information Extraction [MOSTRARE]

Journal title :

Fundamenta Informaticae
Words, Graphs, Automata and Languages. Special Issue Honoring the 60th Birthday of Professor Tero Harju

Pages :

189-204

Publisher :

Polskie Towarzystwo Matematyczne

Publication date :

2012

ISSN :

0169-2968

HAL domain(s) :

Informatique [cs]/Théorie et langage formel [cs.FL]

French abstract :

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 ...
Show more >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.Show less >

English abstract : [en]

The family of one-rule grid semi-Thue systems, introduced by Alfons Geser, is the family of one-rule semi-Thue systems such that there exists a letter c that occurs as often in the left-hand side as the right-hand side of ...
Show more >The family of one-rule grid semi-Thue systems, introduced by Alfons Geser, is the family of one-rule semi-Thue systems such that there exists a letter c that occurs as often in the left-hand side as the right-hand side of the rewriting rule. We prove that for any one-rule grid semi-Thue system S, the set S(w) of all words obtainable from w using repeatedly the rewriting rule of S is a constructible context-free language. We also prove the regularity of the set Loop(S) of all words that start a loop in a one-rule grid semi-Thue systems S.Show less >

Language :

Anglais

Popular science :

Non

Collections :