On One-Rule Grid Semi-Thue Systems

• Autorzy: Latteux M. , Roos Y.
• Języki publikacji: EN

Abstrakty

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 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.

Słowa kluczowe

EN

one-rule semi-Thue system; termination; grid semi-Thue system

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 116, nr 1-4
• Strony: 189--204
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Latteux M.

autor

Roos Y.

• Laboratoire d’Informatique Fondamentale de Lille, Université Lille 1,

Bibliografia

• [1] Anne-Cécile Caron. Linear bounded automata and rewrite systems: Influence of initial configurations on decision properties. In TAPSOFT, Vol.1, pages 74-89, 1991.
• [2] Max Dauchet. Termination of rewriting is undecidable in the one-rule case. In MFCS, pages 262-270, 1988.
• [3] Nachum Dershowitz. Termination of rewriting. J. Symb. Comput., 3(1/2):69-116, 1987.
• [4] Alfons Geser. Decidability of termination of grid string rewriting rules. SIAM J. Comput., 31(4):1156-1168, 2002.
• [5] Alfons Geser. Loops of superexponential lengths in one-rule string rewriting. In RTA, pages 267-280, 2002.
• [6] Alfons Geser. Termination of string rewriting rules that have one pair of overlaps. In RTA, pages 410-423, 2003.
• [7] Alfons Geser and Hans Zantema. Non-looping string rewriting. ITA, 33(3):279-302, 1999.
• [8] Seymour Ginsburg. The Mathematical Theory of Context-Free Languages. McGraw-Hill, Inc., New York, NY, USA, 1966.
• [9] Seymour Ginsburg and Edwin H. Spanier. Bounded algol-like languages. Transactions of the American Mathematical Society, 113(2):333-368, 1964.
• [10] John V. Guttag, Deepak Kapur, and David R. Musser. On proving uniform termination and restricted termination of rewriting systems. SIAM J. Comput., 12(1):189-214, 1983.
• [11] Winfried Kurth. One-rule semi-thue systems with loops of length one, two or three. ITA, 30(5):415-429, 1996.
• [12] Michel Latteux and Yves Roos. The image of a word by a one-rule semi-Thue system is not always contextfree. http://www.lifl.fr/~yroos/al/one-rule-context-free.pdf, 2011.
• [13] Michel Latteux and Yves Roos. A new proof for the uniformtermination problemof one-rule grid semi-Thue systems. http://www.lifl.fr/~yroos/al/one-rule-utermination.pdf, 2011.
• [14] Yuri Matiyasevich and Géraud Sénizergues. Decision problems for semi-thue systems with a few rules. In LICS, pages 523-531, 1996.
• [15] RobertMcnaughton. Well behaved derivations in one-rule semi-thue systems. Technical Report 95-15, Dept. of Computer Science, Rennsselaer Polytechnic Institute, 1995.
• [16] Robert Mcnaughton. Semi-thue systems with an inhibitor. J. Autom. Reason., 26(4):409-431, 2001.
• [17] Wojciech Moczydlowski and Alfons Geser. Termination of single-threaded one-rule semi-thue systems. In RTA, pages 338-352, 2005.
• [18] Masahiko Sakai and Yi Wang. Undecidable properties on length-two string rewriting systems. Electronic Notes in Theoretical Computer Science, 204:53 - 69, 2008. Proceedings of the 7th International Workshop on Reduction Strategies in Rewriting and Programming (WRS 2007).
• [19] Géraud Sénizergues. Some undecidable termination problems for semi-thue systems. Theor. Comput. Sci., 142(2):257-276, 1995.
• [20] Géraud Sénizergues. On the termination problem for one-rule semi-thue system. In RTA, pages 302-316, 1996.
• [21] CeliaWrathall. Confluence of one-rule thue systems. In IWWERT '90: Proceedings of the First International Workshop on Word Equations and Related Topics, pages 237-246, London, UK, 1992. Springer-Verlag.
• [22] Wang Yi, Sakai Masahiko, and Nishida Naoki. Confluence of length preserving string rewriting systems is undecidable(theory of computer science and its applications). RIMS Kokyuroku, 1554:171-177, 2007.
• [23] Hans Zantema and Alfons Geser. A complete characterization of termination of 0p 1q-> 1r 0s. Appl. Algebra Eng. Commun. Comput., 11(1):1-25, 2000.