On One-Rule Grid Semi-Thue Systems

Abstract : 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.
Document type :
Journal articles
Fundamenta Informaticae, IOS Press, 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
Contributor : Yves Roos <>
Submitted on : Wednesday, November 7, 2012 - 11:12:31 AM
Last modification on : Wednesday, November 7, 2012 - 1:38:57 PM

File

on-one-rule-grid-semi-thue-sys...
fileSource_public_author

Identifiers

Collections

Citation

Michel Latteux, Yves Roos. On One-Rule Grid Semi-Thue Systems. Fundamenta Informaticae, IOS Press, 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>

Export

Share

Metrics

Consultation de
la notice

113

Téléchargement du document

24