Skip to Main content Skip to Navigation
New interface
Journal articles

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
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Yves Roos Connect in order to contact the contributor
Submitted on : Wednesday, November 7, 2012 - 11:12:31 AM
Last modification on : Friday, February 4, 2022 - 3:19:28 AM
Long-term archiving on: : Friday, February 8, 2013 - 3:42:50 AM


Files produced by the author(s)



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



Record views


Files downloads