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) no. 5, pp. 415-429.
@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},
pages = {415--429},
publisher = {EDP-Sciences},
volume = {30},
number = {5},
year = {1996},
zbl = {0867.68064},
mrnumber = {1435730},
language = {en},
url = {http://www.numdam.org/item/ITA_1996__30_5_415_0/}
}
TY  - JOUR
AU  - Kurth, Winfried
TI  - One-rule semi-Thue systems with loops of length one, two or three
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1996
DA  - 1996///
SP  - 415
EP  - 429
VL  - 30
IS  - 5
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1996__30_5_415_0/
UR  - https://zbmath.org/?q=an%3A0867.68064
UR  - https://www.ams.org/mathscinet-getitem?mr=1435730
LA  - en
ID  - ITA_1996__30_5_415_0
ER  - 
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) no. 5, pp. 415-429. http://www.numdam.org/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.