×

Elements of finite order for finite monadic Church-Rosser Thue systems. (English) Zbl 0583.20054

Let T be a Thue system over S. The relation \(\leftrightarrow_ T\) is defined for \(u,v\in S^*\) by \(u\leftrightarrow_ Tv\) iff \(\exists x,y\in S^*\), (\(\ell,r)\in T:\) \((u=x\ell y\) and \(v=xry)\) or \((u=xry\) and \(v=x\ell y)\). The reflexive and transitive closure of \(\leftrightarrow_ T\) is denoted by \(\leftrightarrow^*_ T\). A Thue system T over S allows nontrivial elements of finite order if there exist \(u\in S^*\) and integers \(n\geq 0\) and \(k\geq 1\) such that \(u\leftrightarrow^*_ T\ell\) and \(u^{n+k}\leftrightarrow^*_ Tu^ n\), where \(\ell\) is the empty word. The following decision problem is shown to be decidable: for a finite monadic Church-Rosser Thue system T over S, does T allow nontrivial elements of finite order?
Reviewer: J.Grzymala-Busse

MSC:

20M35 Semigroups in automata theory, linguistics, etc.
68Q45 Formal languages and automata
20M05 Free semigroups, generators and relations, word problems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Jürgen Avenhaus, Ronald V. Book, and Craig C. Squier, On expressing commutativity by finite Church-Rosser presentations: a note on commutative monoids, RAIRO Inform. Théor. 18 (1984), no. 1, 47 – 52 (English, with French summary). · Zbl 0542.20038
[2] J. Avenhaus, K. Madlener and F. Otto, Groups presented by finite two-monadic Church-Rosser Thue systems, Technical Report 110/84, Department of Computer Science, University of Kaiserslautern, 1984. · Zbl 0604.20034
[3] J. Berstel, Congruences plus que parfaites et langages algébriques, Séminaire d’Informatique Théorique, Institut de Programmation 1976-1977, pp. 123-147.
[4] Ronald V. Book, Confluent and other types of Thue systems, J. Assoc. Comput. Mach. 29 (1982), no. 1, 171 – 182. · Zbl 0478.68032 · doi:10.1145/322290.322301
[5] Ronald V. Book, When is a monoid a group? The Church-Rosser case is tractable, Theoret. Comput. Sci. 18 (1982), no. 3, 325 – 331. · Zbl 0489.68021 · doi:10.1016/0304-3975(82)90072-X
[6] Ronald V. Book, Decidable sentences of Church-Rosser congruences, Theoret. Comput. Sci. 24 (1983), no. 3, 301 – 312. · Zbl 0525.68015 · doi:10.1016/0304-3975(83)90005-1
[7] Ronald V. Book, Matthias Jantzen, and Celia Wrathall, Monadic Thue systems, Theoret. Comput. Sci. 19 (1982), no. 3, 231 – 251. · Zbl 0488.03020 · doi:10.1016/0304-3975(82)90036-6
[8] Ronald V. Book and Friedrich Otto, Cancellation rules and extended word problems, Inform. Process. Lett. 20 (1985), no. 1, 5 – 11. · Zbl 0561.68030 · doi:10.1016/0020-0190(85)90122-X
[9] Y. Cochet and M. Nivat, Une généralisation des ensembles de Dyck, Israel J. Math. 9 (1971), 389 – 395 (French). · Zbl 0215.56005 · doi:10.1007/BF02771689
[10] Michael A. Harrison, Introduction to formal language theory, Addison-Wesley Publishing Co., Reading, Mass., 1978. · Zbl 0411.68058
[11] John E. Hopcroft and Jeffrey D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley Publishing Co., Reading, Mass., 1979. Addison-Wesley Series in Computer Science. · Zbl 0426.68001
[12] Gérard Lallement, On monoids presented by a single relation, J. Algebra 32 (1974), 370 – 388. · Zbl 0307.20034 · doi:10.1016/0021-8693(74)90146-X
[13] Gérard Lallement, Semigroups and combinatorial applications, John Wiley & Sons, New York-Chichester-Brisbane, 1979. Pure and Applied Mathematics; A Wiley-Interscience Publication. · Zbl 0421.20025
[14] Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Springer-Verlag, Berlin-New York, 1977. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89. · Zbl 0368.20023
[15] Wilhelm Magnus, Abraham Karrass, and Donald Solitar, Combinatorial group theory, Second revised edition, Dover Publications, Inc., New York, 1976. Presentations of groups in terms of generators and relations. · Zbl 0362.20023
[16] A. Markov, The impossibility of algorithms for the recognition of certain properties of associative systems, Doklady Akad. Nauk SSSR (N.S.) 77 (1951), 953 – 956 (Russian).
[17] Andrzej Mostowski, On direct products of theories, J. Symbolic Logic 17 (1952), 1 – 31. · Zbl 0047.00704 · doi:10.2307/2267454
[18] David E. Muller and Paul E. Schupp, Groups, the theory of ends, and context-free languages, J. Comput. System Sci. 26 (1983), no. 3, 295 – 310. · Zbl 0537.20011 · doi:10.1016/0022-0000(83)90003-X
[19] Maurice Nivat, Congruences parfaites et quasi-parfaites, Séminaire P. Dubreil, 25e année (1971/72), Algèbre, Fasc. 1, Exp. No. 7, Secrétariat Mathématique, Paris, 1973, pp. 9 (French). · Zbl 0338.02018
[20] Friedrich Otto, Conjugacy in monoids with a special Church-Rosser presentation is decidable, Semigroup Forum 29 (1984), no. 1-2, 223 – 240. , https://doi.org/10.1007/BF02573327 Paliath Narendran and Friedrich Otto, Complexity results on the conjugacy problem for monoids, Theoret. Comput. Sci. 35 (1985), no. 2-3, 227 – 243. , https://doi.org/10.1016/0304-3975(85)90016-7 Paliath Narendran, Friedrich Otto, and Karl Winklmann, The uniform conjugacy problem for finite Church-Rosser Thue systems is NP-complete, Inform. and Control 63 (1984), no. 1-2, 58 – 66. · Zbl 0592.03025 · doi:10.1016/S0019-9958(84)80041-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.