On One-Rule Grid Semi-Thue Systems

Issue title: Words, Graphs, Automata, and Languages; Special Issue Honoring the 60th Birthday of Professor Tero Harju

Article type: Research Article

Authors: Latteux, Michel | Roos, Yves

Affiliations: Laboratoire d'Informatique Fondamentale de Lille, Université Lille 1, michel.latteux@lifl.fr | Laboratoire d'Informatique Fondamentale de Lille, Université Lille 1, yves.roos@lifl.fr

Note: [] Address for correspondence: Laboratoire d'Informatique Fondamentale de Lille Université Lille 1, Cité scientifique - Bâtiment M3 59655 Villeneuve d'Ascq Cédex – France

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.

Keywords: one-rule semi-Thue system, termination, grid semi-Thue system

DOI: 10.3233/FI-2012-678

Journal: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 189-204, 2012