@article{ITA_1999__33_3_279_0, author = {Geser, Alfons and Zantema, Hans}, title = {Non-looping string rewriting}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {279--301}, publisher = {EDP-Sciences}, volume = {33}, number = {3}, year = {1999}, mrnumber = {1728428}, zbl = {0951.68054}, language = {en}, url = {http://www.numdam.org/item/ITA_1999__33_3_279_0/} }
TY - JOUR AU - Geser, Alfons AU - Zantema, Hans TI - Non-looping string rewriting JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 1999 SP - 279 EP - 301 VL - 33 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/item/ITA_1999__33_3_279_0/ LA - en ID - ITA_1999__33_3_279_0 ER -
%0 Journal Article %A Geser, Alfons %A Zantema, Hans %T Non-looping string rewriting %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 1999 %P 279-301 %V 33 %N 3 %I EDP-Sciences %U http://www.numdam.org/item/ITA_1999__33_3_279_0/ %G en %F ITA_1999__33_3_279_0
Geser, Alfons; Zantema, Hans. Non-looping string rewriting. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) no. 3, pp. 279-301. http://www.numdam.org/item/ITA_1999__33_3_279_0/
[1] Problems of equality and divisibility in semigroups with a single defining relation. Mat. Zametki 41 (1987) 412-421. | Zbl
and ,[2] String-rewriting systems. Texts and Monographs in Computer Science. Springer, New York (1993). | MR | Zbl
and ,[3] Termination of linear rewriting Systems. In Proc. of the 8th International Colloquium on Automata, Languages and Programming (ICALP81), Springer, Lecture Notes in Computer Science 115 (1981) 448-458. | MR | Zbl
,[4] Termination of rewriting. J. Symb. Comput. 3 (1987) 69-115; Corrigendum 4 (1987) 409-410. | MR
,[5] Natural termination. Theoret. Comput. Sci. 142 (1995) 179-207. | MR | Zbl
and ,[6] Dummy elimination: Making termination easier. In Proc. l0th Conf. Fundamentals of Computation Theory, H. Reichel, Ed., Springer, Lecture Notes in Computer Science 965 (1995) 243-252. | MR
and ,[7] Termination of one-rule string rewriting Systems l → r where |r| ≤ 9. Tech. Rep., Universität Tübingen, D (Jan. 1998).
,[8] On proving uniform termination and restricted termination of rewriting systems. SIAM J. Comput. 12 (1983) 189-214. | MR | Zbl
, and ,[9] On the uniform halting problem for term rewriting Systems. Rapport Laboria 283, INRIA (1978).
and ,[10] Confluent string rewriting, Vol. 14 of EATCS Monographs on Theoretical Computer Science. Springer, Berlin (1988). | MR | Zbl
,[11] Termination and derivational complexity of confluent one-rule string rewriting Systems. Tech. Rep., Dept. of Computer Science, Toho University, JP (1997).
, and ,[12] Termination und Konfluenz von Semi-Thue-Systemen mit nur einer Regel. Dissertation, Technische Universität Clausthal, Germany (1990). | Zbl
,[13] One-rule semi-Thue Systems with loops of length one, two, or three. RAIRO Theoret. Informatics Appl. 30 (1995) 415-429. | Numdam | Zbl
,[14] A finite termination criterion. Tech. Rep., Information Sciences Institute, Univ. of Southern California, Marina-del-Rey, CA (1978).
and ,[15] Decision problems for semi-Thue systems with a few rules. In IEEE Symp. Logic in Computer Sdence'96 (1996).
and ,[16] The uniform halting problem for one-rule Semi-Thue Systems. Tech. Rep. 94-18, Dept. of Computer Science, Rensselaer Polytechnic Institute, Troy, NY, Aug. 1994.
,See also "Correction to The Uniform Halting Problem for One-rule Semi-Thue Systems", Personal communication (Aug. 1996).
[17] Well-behaved derivations in one-rule Semi-Thue Systems. Tech. Rep. 95-15, Dept. of Computer Science, Rensselaer Polytechnic Institute, Troy, NY (Nov. 1995).
,[18] Semi-Thue Systems with an inhibitor. Tech. Rep. 97-5, Dept. of Computer Science, Rensselaer Polytechnic Institute, Troy, NY (1 1997).
,[19] The undecidability of self-embedding for finite semi-Thue and Thue Systems. Theoret. Comput. Sci. 47 (1986) 225-232. | MR | Zbl
,[20] Tree-manipulating Systems and Church-Rosser Theorems.J. ACM 20 (1973). 160-187. | MR | Zbl
,[21] On termination of confluent one-rule string rewriting Systems. Inform. Process, Lett. 61 (1997), 91-96. | MR
, and ,[22] Confluence of one-rule Thue Systems. In Word Equations and Related Topics, K.U. Schulz, Ed., Springer, Lecture Notes in Computer Science 572 (1991). | MR
,[23] A complete characterization of termination of 0p1q → lr0s. Applicable Algebra in Engineering, Communication, and Computing. In print. | Zbl
and ,[24] A complete characterization of termination of 0p1q → lr0s. In Proc. of the 6th Conference on Rewriting Techniques and Applications, J. Hsiang, Ed., Springer, Lecture Notes in Computer Science 914 (1995) 41-55.
and ,