Decidability of Termination of Grid String Rewriting Rules
Author:
- Alfons GeserAGAlfons Geser
- 1 January 2002
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 31 (4) , 1156-1168
Abstract
Termination of string rewriting is known undecidable. Termination of string rewriting with only one rule is neither known decidable nor known undecidable. This paper presents a decision procedure for rules $u\rightarrow v$ such that some letter b from u occurs as often or less often in v. We call such rules "grid" rules. By far most rules are grid rules. Grid rules cover all rules which terminate by a total division order. Thus total division orders are shown to be irrelevant for the termination problem of one-rule string rewriting.
Keywords
This publication has 8 references indexed in Scilit:
- Termination and derivational complexity of confluent one-rule string-rewriting systemsTheoretical Computer Science, 2001
- A Complete Characterization of Termination of 0 p 1 q → 1 r 0 sApplicable Algebra in Engineering, Communication and Computing, 2000
- On termination of confluent one-rule string-rewriting systemsInformation Processing Letters, 1997
- One-rule semi-Thue systems with loops of length one, two or threeRAIRO - Theoretical Informatics and Applications, 1996
- Rationality of division orderingsInformation Processing Letters, 1992
- Simulation of Turing machines by a regular rewrite ruleTheoretical Computer Science, 1992
- Calcul de longueurs de chaînes de réécriture dans le monoïde libreTheoretical Computer Science, 1985
- Ordering by Divisibility in Abstract AlgebrasProceedings of the London Mathematical Society, 1952