Groups presented by finite two-monadic Church-Rosser Thue systems

Avenhaus, J.; Madlener, K.; Otto, F.

doi:10.1090/S0002-9947-1986-0854076-5

Groups presented by finite two-monadic Church-Rosser Thue systems
HTML articles powered by AMS MathViewer

by J. Avenhaus, K. Madlener and F. Otto PDF

Trans. Amer. Math. Soc. 297 (1986), 427-443 Request permission

Abstract:

It is shown that a group $G$ can be defined by a monoid-presentation of the form $(\Sigma ;T)$, where $T$ is a finite two-monadic Church-Rosser Thue system over $\Sigma$, if and only if $G$ is isomorphic to the free product of a finitely generated free group with a finite number of finite groups.

References

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). MR 0498062, DOI 10.1007/bf00263767
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. MR 875854
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). MR 750450, DOI 10.1051/ita/1984180100471
Ronald V. Book, Confluent and other types of Thue systems, J. Assoc. Comput. Mach. 29 (1982), no. 1, 171–182. MR 662617, DOI 10.1145/322290.322301

The power of the Church-Rosser property in string rewriting systems

Ronald V. Book, When is a monoid a group? The Church-Rosser case is tractable, Theoret. Comput. Sci. 18 (1982), no. 3, 325–331. MR 662676, DOI 10.1016/0304-3975(82)90072-X
Ronald V. Book, Matthias Jantzen, and Celia Wrathall, Monadic Thue systems, Theoret. Comput. Sci. 19 (1982), no. 3, 231–251. MR 671869, DOI 10.1016/0304-3975(82)90036-6
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). MR 0066372
B. Buchberger and R. Loos, Algebraic simplification, Computer algebra, Springer, Vienna, 1983, pp. 11–43. MR 728962
Frank B. Cannonito, Hierarchies of computable groups and the word problem, J. Symbolic Logic 31 (1966), 376–392. MR 224471, DOI 10.2307/2270453
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. MR 541109
M. Dehn, Über unendliche diskontinuierliche Gruppen, Math. Ann. 71 (1911), no. 1, 116–144 (German). MR 1511645, DOI 10.1007/BF01456932
Robert H. Haring-Smith, Groups and simple languages, Trans. Amer. Math. Soc. 279 (1983), no. 1, 337–356. MR 704619, DOI 10.1090/S0002-9947-1983-0704619-4
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. MR 743114
Gérard Lallement, Semigroups and combinatorial applications, Pure and Applied Mathematics, John Wiley & Sons, New York-Chichester-Brisbane, 1979. MR 530552
Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89, Springer-Verlag, Berlin-New York, 1977. MR 0577064
W. Magnus, Das Identitätsproblem für Gruppen mit einer definierenden Relation, Math. Ann. 106 (1932), no. 1, 295–307 (German). MR 1512760, DOI 10.1007/BF01455888
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. MR 0422434
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. MR 710250, DOI 10.1016/0022-0000(83)90003-X
P. S. Novikov, Ob algoritmičeskoĭ nerazrešimosti problemy toždestva slov v teorii grupp, Izdat. Akad. Nauk SSSR, Moscow, 1955 (Russian). Trudy Mat. Inst. Steklov. no. 44. MR 0075197
Friedrich Otto, Conjugacy in monoids with a special Church-Rosser presentation is decidable, Semigroup Forum 29 (1984), no. 1-2, 223–240. MR 742135, DOI 10.1007/BF02573327
Michael O. Rabin, Recursive unsolvability of group theoretic problems, Ann. of Math. (2) 67 (1958), 172–194. MR 110743, DOI 10.2307/1969933
John Stallings, Group theory and three-dimensional manifolds, Yale Mathematical Monographs, vol. 4, Yale University Press, New Haven, Conn.-London, 1971. A James K. Whittemore Lecture in Mathematics given at Yale University, 1969. MR 0415622