One-rule semi-Thue systems with loops of length one, two or three
Kurth, Winfried
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996), p. 415-429 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1996__30_5_415_0,
     author = {Kurth, Winfried},
     title = {One-rule semi-Thue systems with loops of length one, two or three},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {30},
     year = {1996},
     pages = {415-429},
     mrnumber = {1435730},
     zbl = {0867.68064},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1996__30_5_415_0}
}

Kurth, Winfried. One-rule semi-Thue systems with loops of length one, two or three. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) pp. 415-429. http://gdmltest.u-ga.fr/item/ITA_1996__30_5_415_0/

1. H. Abdulrab, Solving Word Equations, RAIRO Theo. Informatics and Appl., 1990, 24, pp. 109-130. | Numdam | MR 1073531 | Zbl 0701.68053

2. A. C. Caron, Linear Bounded Automata and Rewrite Systems: Influence of Initial Configurations on Decision Properties. Proceedings of TAPSOFT 91, April 8-12, 1991, Brighton, England, LNCS, 1991, 493, pp. 74-89. | MR 1107773 | Zbl 0967.68523

3. M. Dauchet, Termination of Rewriting is Undecidable in the One-rule Case. Proc. 13th Symposium MFCS, August 29-Sept. 2, 1988, Carlsbad, Czech., LNCS, 1988, 324, pp. 262-270. | MR 1023430 | Zbl 0649.68026

4. N. Dershowitz, Termination of Rewriting. J. Symbolic Computation, 1987, 3, pp. 69-116, and 1987, 4, pp. 409-410. | MR 925736

5. C. Kirchner (Ed.), Rewriting Techniques and Applications, Proceedings of RTA-93, June 16-18, 1993, Montréal, Canada. LNCS, 1993, 690. | MR 1251780 | Zbl 0825.00068

6. W. Kurth, Termination und Konfluenz von Semi-Thue-Systemen mit nur einer Regel, Dissertation, Technische Universität Clausthal, 1990. | Zbl 0719.03019

7. G. Lallement, On Monoids Presented by a Single Relation. J. Algebra, 1974, 32, pp. 370-388. | MR 354908 | Zbl 0307.20034

8. R. Mcnaughton, The Uniform Halting Problem for One-Rule Semi-Thue Systems, Rensselaer Polytechnic Institute, Report 94-18, August 1994.

9. R. Mcnaughton, Well Behaved Derivations in One-Rule Semi-Thue Systems, Rensselaer Polytechnic Institute, Report 95-15, November 1995.

10. Y. Metivier, Calcul de Longueurs de Chaînes de Réécriture dans le Monoïde Libre, Theoretical Computer Science, 1985, 35, pp. 71-87. | MR 785908 | Zbl 0562.03019

11. P. Narendran, C. Ó'Dunlaing and H. Rolletschek, Complexity of Certain Decision Problems About Congruential Languages, J. Computer Syst. Sci., 1985, 30, pp. 343-358. | MR 805653 | Zbl 0607.68055

12. F. Otto, The Undecidability of Self-Embedding for Finite Semi-Thue and Thue Systems, Theoretical Computer Science, 1986, 47, pp. 225-232. | MR 881214 | Zbl 0624.03032

13. H. Zantema and A. Geser, A complete characterization of termination of 0p 1q → 1r 0s. Proceedings of RTA-95, April 5-7, 1995, Kaiserslautern, Germany, LNCS, 1995, 914, pp. 41-55.