×

Groups presented by finite two-monadic Church-Rosser Thue systems. (English) Zbl 0604.20034

In this interesting paper the authors give a characterization of the groups which can have a presentation by a (finite) Church-Rosser Thue system. After giving detailed and clear definitions of the concepts of Thue systems, Church-Rosser systems and monadic and special Thue systems, the authors prove their main results which says that a group G has a presentation (\(\Sigma\) ;T) such that \(T\subseteq \Sigma^ 2\times (\Sigma \cup \{1\})\), where \(\Sigma\) is a finite set (of generators), is finite and Church-Rosser if and only if G is a free product of a finitely generated free group and of a finite number of finite groups. Details of the proofs or the definitions are impossible to be given here. Their main result is a refinement and an extension of an analogous result of the first two authors [Algebra, combinatorics, and logic in computer science, Colloq. Math. Soc. János Bolyai 42, 63-71 (1986)].
Reviewer: S.Andreadakis

MSC:

20F05 Generators, relations, and presentations of groups
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20E06 Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Avenhaus and K. Madlener, Subrekursive Komplexität bei Gruppen. I. Gruppen mit vorgeschriebener Komplexität, Acta Informat. 9 (1977/78), no. 1, 87 – 104 (German, with English summary). · Zbl 0371.02019
[2] J. Avenhaus and K. Madlener, On groups defined by monadic Thue systems, Algebra, combinatorics and logic in computer science, Vol. I, II (Győr, 1983) Colloq. Math. Soc. János Bolyai, vol. 42, North-Holland, Amsterdam, 1986, pp. 63 – 71. · Zbl 0608.20045
[3] 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
[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] -, The power of the Church-Rosser property in string rewriting systems, Proc. 6th Conf. on Automated Deduction, 1982, pp. 360-368.
[6] 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
[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] William W. Boone, Certain simple, unsolvable problems of group theory. I, Nederl. Akad. Wetensch. Proc. Ser. A. 57 (1954), 231 – 237 = Indag. Math. 16, 231 – 237 (1954). · Zbl 0055.00602
[9] B. Buchberger and R. Loos, Algebraic simplification, Computer algebra, Springer, Vienna, 1983, pp. 11 – 43. · Zbl 0494.68045
[10] Frank B. Cannonito, Hierarchies of computable groups and the word problem, J. Symbolic Logic 31 (1966), 376 – 392. · Zbl 0178.32502 · doi:10.2307/2270453
[11] Y. Cochet, Church-Rosser congruences on free semigroups, Algebraic theory of semigroups (Proc. Sixth Algebraic Conf., Szeged, 1976), Colloq. Math. Soc. János Bolyai, vol. 20, North-Holland, Amsterdam-New York, 1979, pp. 51 – 60. · Zbl 0408.20054
[12] M. Dehn, Über unendliche diskontinuierliche Gruppen, Math. Ann. 71 (1911), no. 1, 116 – 144 (German). · JFM 42.0508.03 · doi:10.1007/BF01456932
[13] Robert H. Haring-Smith, Groups and simple languages, Trans. Amer. Math. Soc. 279 (1983), no. 1, 337 – 356. · Zbl 0518.20030
[14] D. Kapur and P. Narendran, The Knuth-Bendix completion procedure and Thue systems, Foundations of software technology and theoretical computer science (Bangalore, 1983) Tata Inst. Fund. Res., Bombay, 1983, pp. 363 – 385. · Zbl 0535.68012
[15] 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
[16] 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
[17] W. Magnus, Das Identitätsproblem für Gruppen mit einer definierenden Relation, Math. Ann. 106 (1932), no. 1, 295 – 307 (German). · JFM 58.0125.01 · doi:10.1007/BF01455888
[18] 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
[19] 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
[20] P. S. Novikov, Ob algoritmičeskoĭ nerazrešimosti problemy toždestva slov v teorii grupp, Trudy Mat. Inst. im. Steklov. no. 44, Izdat. Akad. Nauk SSSR, Moscow, 1955 (Russian).
[21] 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
[22] Michael O. Rabin, Recursive unsolvability of group theoretic problems, Ann. of Math. (2) 67 (1958), 172 – 194. · Zbl 0079.24802 · doi:10.2307/1969933
[23] John Stallings, Group theory and three-dimensional manifolds, Yale University Press, New Haven, Conn.-London, 1971. A James K. Whittemore Lecture in Mathematics given at Yale University, 1969; Yale Mathematical Monographs, 4. · Zbl 0241.57001
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.