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

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

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

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
ISSN 1088-6850(online) ISSN 0002-9947(print)

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

Authors: J. Avenhaus, K. Madlener and F. Otto
Journal: Trans. Amer. Math. Soc. 297 (1986), 427-443
MSC: Primary 20F10; Secondary 03D03, 03D40, 20F05
MathSciNet review: 854076
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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

[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). MR 0498062 (58 #16239)
[2] J. Avenhaus and K. Madlener, On groups defined by monadic Thue systems, (Győr, 1983) Colloq. Math. Soc. János Bolyai, vol. 42, North-Holland, Amsterdam, 1986, pp. 63–71. MR 875854 (88f:20054)
[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). MR 750450 (85j:03057)
[4] Ronald V. Book, Confluent and other types of Thue systems, J. Assoc. Comput. Mach. 29 (1982), no. 1, 171–182. MR 662617 (84c:03076), http://dx.doi.org/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. MR 662676 (84b:20067), http://dx.doi.org/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. MR 671869 (84d:03048), http://dx.doi.org/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). MR 0066372 (16,564d)
[9] B. Buchberger and R. Loos, Algebraic simplification, Computer algebra, Springer, Vienna, 1983, pp. 11–43. MR 728962
[10] Frank B. Cannonito, Hierarchies of computable groups and the word problem, J. Symbolic Logic 31 (1966), 376–392. MR 0224471 (37 #70)
[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, 1979, pp. 51–60. MR 541109 (80i:03051)
[12] M. Dehn, Über unendliche diskontinuierliche Gruppen, Math. Ann. 71 (1911), no. 1, 116–144 (German). MR 1511645, http://dx.doi.org/10.1007/BF01456932
[13] Robert H. Haring-Smith, Groups and simple languages, Trans. Amer. Math. Soc. 279 (1983), no. 1, 337–356. MR 704619 (85b:20045), http://dx.doi.org/10.1090/S0002-9947-1983-0704619-4
[14] D. Kapur and P. Narendran, The Knuth-Bendix completion procedure and Thue systems, (Bangalore, 1983) Tata Inst. Fund. Res., Bombay, 1983, pp. 363–385. MR 743114 (85e:68040)
[15] Gérard Lallement, Semigroups and combinatorial applications, John Wiley & Sons, New York-Chichester-Brisbane, 1979. Pure and Applied Mathematics; A Wiley-Interscience Publication. MR 530552 (81j:20082)
[16] Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Springer-Verlag, Berlin, 1977. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89. MR 0577064 (58 #28182)
[17] W. Magnus, Das Identitätsproblem für Gruppen mit einer definierenden Relation, Math. Ann. 106 (1932), no. 1, 295–307 (German). MR 1512760, http://dx.doi.org/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. MR 0422434 (54 #10423)
[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. MR 710250 (84k:20016), http://dx.doi.org/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). MR 0075197 (17,706b)
[21] Friedrich Otto, Conjugacy in monoids with a special Church-Rosser presentation is decidable, Semigroup Forum 29 (1984), no. 1-2, 223–240. MR 742135 (87h:20107a), http://dx.doi.org/10.1007/BF02573327
[22] Michael O. Rabin, Recursive unsolvability of group theoretic problems, Ann. of Math. (2) 67 (1958), 172–194. MR 0110743 (22 #1611)
[23] John Stallings, Group theory and three-dimensional manifolds, Yale University Press, New Haven, Conn., 1971. A James K. Whittemore Lecture in Mathematics given at Yale University, 1969; Yale Mathematical Monographs, 4. MR 0415622 (54 #3705)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|