World Scientific
  • Search
    Quick Search in Journals
    Access type:
    Quick Search anywhere
    Access type:
    Advanced Search
  • My Cart
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

Our site uses Javascript to enchance its usability.You can disable your ad blocker or whitelist our website www.worldscientific.com to view the full content.

Select your blocker:

Adblock Plus Instructions

  1. Click the AdBlock Plus icon in the extension bar
  2. Click the blue power button
  3. Click refresh

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
No Access

On one-relator groups and units of special one-relation inverse monoids

    https://doi.org/10.1142/S0218196722500618Cited by:1 (Source: Crossref)
    Previous
    Next

    Abstract

    This paper investigates and clarifies some connections between the theory of one-relator groups and special one-relation inverse monoids, i.e. those inverse monoids with a presentation of the form Inv〈A|w=1〉. We show that every one-relator group admits a special one-relation inverse monoid presentation. We subsequently consider the classes any,red,cred,pos of one-relator groups which can be defined by special one-relation inverse monoid presentations in which the defining word is arbitrary; reduced; cyclically reduced; or positive, respectively. We show that the inclusions any⊃cred⊃pos are all strict. Conditional on a natural conjecture, we prove any⊃red. Following this, we use the Benois algorithm recently devised by Gray and Ruškuc to produce an infinite family of special one-relation inverse monoids which exhibit similar pathological behavior (which we term O’Haresque) to the O’Hare monoid with respect to computing the minimal invertible pieces of the defining word. Finally, we provide a counterexample to a conjecture by Gray and Ruškuc that the Benois algorithm always correctly computes the minimal invertible pieces of a special one-relation inverse monoid.

    Communicated by M. Lawson

    AMSC: 20M18, 20M05, 20F05

    References

    • 1. S. I. Adian, Algorithmic unsolvability of problems of recognition of certain properties of groups, Dokl. Akad. Nauk SSSR 103 (1955) 533–535. Google Scholar
    • 2. S. I. Adian, The problem of identity in associative systems of a special form, Soviet Math. Dokl. 1 (1960) 1360–1363. Google Scholar
    • 3. S. I. Adian, Defining relations and algorithmic problems for groups and semigroups, Trudy Mat. Inst. Steklov. 85 (1966) 123. Google Scholar
    • 4. G. Baumslag, A non-cyclic one-relator group all of whose finite quotients are cyclic, J. Austral. Math. Soc. 10 (1969) 497–498. Crossref, Google Scholar
    • 5. G. Baumslag, Positive one-relator groups, Trans. Amer. Math. Soc. 156 (1971) 165–183. Crossref, Web of Science, Google Scholar
    • 6. M. Benois, Parties rationnelles du groupe libre, C. R. Acad. Sci. Paris Sér. A-B 269 (1969) A1188–A1190. Google Scholar
    • 7. J.-Camille Birget, S. W. Margolis and J. C. Meakin, The word problem for inverse monoids presented by one idempotent relator, Theor. Comput. Sci. 123(2) (1994) 273–289. Crossref, Web of Science, Google Scholar
    • 8. R. V. Book, M. Jantzen and C. Wrathall, Monadic Thue systems, Theor. Comput. Sci. 19(3) (1982) 231–251. Crossref, Web of Science, Google Scholar
    • 9. W. W. Boone, An analysis of Turing’s: The word problem in semi-groups with cancellation, Ann. Math. 67 (1958) 195–202. Crossref, Web of Science, Google Scholar
    • 10. W. W. Boone, The word problem, Proc. Nat. Acad. Sci. USA 44 (1958) 1061–1065. Crossref, Web of Science, Google Scholar
    • 11. H. Calbrix, La théorie monadique du second ordre du monoïde inversif libre est indécidable, Bull. Belg. Math. Soc. Simon Stevin 4(1) (1997) 53–65. Crossref, Google Scholar
    • 12. A. Church, Combinatory logic as a semi-group, Bull. Amer. Math. Soc. 43 (1937) 333. Google Scholar
    • 13. M. Dehn, Über unendliche diskontinuierliche Gruppen, Math. Ann. 71(1) (1911) 116–144. Crossref, Google Scholar
    • 14. M. Dehn, Die beiden Kleeblattschlingen, Math. Ann. 75(3) (1914) 402–413. Crossref, Google Scholar
    • 15. I. Dolinka and R. D. Gray, New results on the prefix membership problem for one-relator groups, Trans. Amer. Math. Soc. 374(6) (2021) 4309–4358. Crossref, Web of Science, Google Scholar
    • 16. W. Dyck, Gruppentheoretische studien, Math. Ann. 20(1) (1882) 1–44. Crossref, Google Scholar
    • 17. S. M. Gersten, Dehn functions and l1-norms of finite presentations, in Algorithms and Classification in Combinatorial Group Theory (Berkeley, CA, 1989), Mathematical Science Research Institute Publications, Vol. 23 (Springer, New York, 1992), pp. 195–224. Crossref, Google Scholar
    • 18. R. D. Gray, Undecidability of the word problem for one-relator inverse monoids via right-angled Artin subgroups of one-relator groups, Invent. Math. 219(3) (2020) 987–1008. Crossref, Web of Science, Google Scholar
    • 19. R. D. Gray and N. Ruškuc, On groups of units of special and one-relator inverse monoids, preprint (2021), arXiv:2103.02995. Google Scholar
    • 20. R. D. Gray and B. Steinberg, Free inverse monoids are not FP2, Comptes Rendus de l‘Acad. des Sci. — Series I: Math. 359 (2021) 1047–1057. Google Scholar
    • 21. S. Hermiller, S. Lindblad and J. Meakin, Decision problems for inverse monoids presented by a single sparse relator, Semigroup Forum 81(1) (2010) 128–144. Crossref, Web of Science, Google Scholar
    • 22. S. Eberhard (https://math.stackexchange.com/users/23805/sean eberhard), Prefixes of a word multiplying to the identity in a free group, Mathematics Stack Exchange (2021), https://math.stackexchange.com/q/4304313. Google Scholar
    • 23. S. V. Ivanov, S. W. Margolis and J. C. Meakin, On one-relator inverse monoids and one-relator groups, J. Pure Appl. Algebra 159(1) (2001) 83–111. Crossref, Web of Science, Google Scholar
    • 24. M. Kambites, P. V. Silva and B. Steinberg, On the rational subset problem for groups, J. Algebra 309(2) (2007) 622–639. Crossref, Web of Science, Google Scholar
    • 25. G. Lallement, On monoids presented by a single relation, J. Algebra 32 (1974) 370–388. Crossref, Web of Science, Google Scholar
    • 26. R. C. Lyndon and P. E. Schupp, Combinatorial Group Theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (Springer-Verlag, Berlin, New York, 1977). Crossref, Google Scholar
    • 27. W. Magnus, Das Identitätsproblem für Gruppen mit einer definierenden Relation, Math. Ann. 106(1) (1932) 295–307. Crossref, Google Scholar
    • 28. W. Magnus, Über diskontinuierliche Gruppen mit einer definierenden Relation. (Der Freiheitssatz), J. Reine Angew. Math. 163 (1930) 141–165. Crossref, Google Scholar
    • 29. W. Magnus, A. Karrass and D. Solitar, Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations (Interscience Publishers, John Wiley & Sons, Inc., New York, London, Sydney, 1966). Google Scholar
    • 30. G. S. Makanin, On the identity problem for finitely presented groups and semigroups, Ph.D. thesis, Steklov Mathematical Institute, Moscow (1966). Google Scholar
    • 31. G. S. Makanin, On the identity problem in finitely defined semigroups, Dokl. Akad. Nauk SSSR 171 (1966) 285–287. Google Scholar
    • 32. G. S. Makanin, The problem of the solvability of equations in a free semigroup, Mat. Sb. 103(145) (2) (1977) 147–236, 319. Google Scholar
    • 33. G. S. Makanin, Equations in a free group, Izv. Akad. Nauk SSSR Ser. Mat. 46(6) (1982) 1199–1273, 1344. Google Scholar
    • 34. S. W. Margolis, J. C. Meakin and J. B. Stephen, Free objects in certain varieties of inverse semigroups, Canad. J. Math. 42(6) (1990) 1084–1097. Crossref, Web of Science, Google Scholar
    • 35. S. W. Margolis, J. Meakin and Z. Šuniḱ, Distortion functions and the membership problem for submonoids of groups and monoids, in Geometric Methods in Group Theory, Contemporary Mathematics (American Mathematical Society, Providence, RI, 2005), pp. 109–129. Crossref, Google Scholar
    • 36. S. W. Margolis and J. C. Meakin, Inverse monoids, trees and context-free languages, Trans. Amer. Math. Soc. 335(1) (1993) 259–276. Web of Science, Google Scholar
    • 37. S. W. Margolis, J. C. Meakin and J. B. Stephen, Some decision problems for inverse monoid presentations, in Semigroups and Their Applications (Chico, Calif., 1986), (Reidel, Dordrecht, 1987), pp. 99–110. Google Scholar
    • 38. A. Markov, The impossibility of certain algorithms in the theory of associative systems, II, Doklady Akad. Nauk SSSR 58 (1947) 353–356. Google Scholar
    • 39. A. Markov, On the impossibility of certain algorithms in the theory of associative systems, C. R. (Doklady) Acad. Sci. URSS 55 (1947)  583–586. Google Scholar
    • 40. A. A. Markov, The impossibility of algorithms for the recognition of certain properties of associative systems, Doklady Akad. Nauk SSSR 77 (1951) 953–956. Google Scholar
    • 41. J. McCool and A. Pietrowski, On free products with amalgamation of two infinite cyclic groups, J. Algebra 18 (1971) 377–383. Crossref, Web of Science, Google Scholar
    • 42. W. D. Munn, Free inverse semigroups, Proc. Lond. Math. Soc. 29 (1974) 385–404. Crossref, Web of Science, Google Scholar
    • 43. A. Myasnikov, A. Ushakov and D. W. Won, The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable, J. Algebra 345 (2011) 324–342. Crossref, Web of Science, Google Scholar
    • 44. P. S. Novikov, On algorithmic unsolvability of the problem of identity, Doklady Akad. Nauk SSSR 85 (1952) 709–712. Google Scholar
    • 45. P. S. Novikov and S. I. Adian, Das Wortproblem für Halbgruppen mit einseitiger Kürzungsregel, Z. Math. Logik Grundlagen Math. 4 (1958) 66–88. Google Scholar
    • 46. C.-F. Nyberg-Brodda, The word problem and combinatorial methods for groups and semigroups, Ph.D. thesis, university of East Anglia, UK (2021). Google Scholar
    • 47. C.-F. Nyberg-Brodda, The word problem for one-relation monoids: A survey, Semigroup Forum 103(2) (2021) 297–355. Crossref, Web of Science, Google Scholar
    • 48. C.-F. Nyberg-Brodda, On the word problem for special monoids, Semigroup Forum 105 (2022) 295–327. Crossref, Web of Science, Google Scholar
    • 49. C.-F. Nyberg-Brodda, A translation of G. S. Makanin’s 1966 Ph.D. thesis “On the Identity Problem for Finitely Presented Groups and Semigroups” (2021), arXiv:2102.00745 Google Scholar
    • 50. F. Otto, An example of a one-relator group that is not a one-relation monoid, Discrete Math. 69(1) (1988) 101–103. Crossref, Web of Science, Google Scholar
    • 51. D. Perrin and P. Schupp, Sur les monoïdes à un relateur qui sont des groupes, Theor. Comput. Sci. 33(2–3) (1984) 331–334. Crossref, Google Scholar
    • 52. M. Petrich, Inverse Semigroups, Pure and Applied Mathematics (John Wiley & Sons, Inc., New York, 1984). Google Scholar
    • 53. E. L. Post, Recursive unsolvability of a problem of Thue, J. Symbolic Logic 12 (1947) 1–11. Crossref, Google Scholar
    • 54. M. O. Rabin, Recursive unsolvability of group theoretic problems, Ann. Math. 67 (1958) 172–194. Crossref, Web of Science, Google Scholar
    • 55. N. R. Reilly, Free generators in free inverse semigroups, Bull. Austral. Math. Soc. 7 (1972) 407–424. Crossref, Google Scholar
    • 56. B. V. Rozenblat, Positive theories of free inverse semigroups, Sibirsk. Mat. Zh. 20(6) (1979) 1282–1293. Web of Science, Google Scholar
    • 57. B. V. Rozenblat, Diophantine theories of free inverse semigroups, Sibirsk. Mat. Zh. 26(6) (1985) 101–107, 190. Web of Science, Google Scholar
    • 58. N. Ruškuc, Semigroup presentations, Ph.D., thesis, University of St Andrews (1995). Google Scholar
    • 59. H. E. Scheiblich, Free inverse semigroups, Semigroup Forum 4 (1972) 351–359. Crossref, Google Scholar
    • 60. H. E. Scheiblich, Free inverse semigroups, Proc. Amer. Math. Soc. 38 (1973) 1–7. Crossref, Web of Science, Google Scholar
    • 61. B. M. Schein, Free inverse semigroups are not finitely presentable, Acta Math. Acad. Sci. Hungar. 26 (1975) 41–52. Crossref, Web of Science, Google Scholar
    • 62. P. V. Silva, Rational languages and inverse monoid presentations, Int. J. Algebra Comput. 2(2) (1992) 187–207. Link, Google Scholar
    • 63. J. B. Stephen, Applications of automata theory to presentations of monoids and inverse monoids, Ph. D., thesis, The University of Nebraska, Lincoln (1987). Google Scholar
    • 64. J. B. Stephen, Presentations of inverse monoids, J. Pure Appl. Algebra 63(1) (1990)  81–112. Crossref, Web of Science, Google Scholar
    • 65. J. B. Stephen, The word problem for inverse monoids and related questions, in Monoids and Semigroups with Applications (Berkeley, CA, 1989) (World Scientific Publication, River Edge, New Jersey, 1991), pp. 129–143. Google Scholar
    • 66. J. B. Stephen, Contractive presentations: A family of inverse monoids and semigroups with finite ℛ-classes, Semigroup Forum 44(2) (1992)  255–270. Crossref, Web of Science, Google Scholar
    • 67. J. B. Stephen, Inverse monoids and rational subsets of related groups, Semigroup Forum 46(1) (1993) 98–108. Crossref, Web of Science, Google Scholar
    • 68. J. B. Stephen, Amalgamated free products of inverse semigroups, J. Algebra 208(2) (1998) 399–424. Crossref, Web of Science, Google Scholar
    • 69. A. Thue, Problem über Veränderungen von Zeichenreihen nach gegebenen Regeln, Christiana Videnskaps-Selskabs Skrifter, I. Math. Naturv. Klasse 10 (1914) 1–34. Google Scholar
    • 70. A. M. Turing, The word problem in semi-groups with cancellation, Ann. Math. 52 (1950) 491–505. Crossref, Web of Science, Google Scholar
    • 71. V. V. Wagner, Generalised heaps and generalised groups with transitive compatibility relation, Uchen. Zap. Saratov. Univ. 70 (1961) 25–39. Google Scholar
    • 72. L. Zhang, Conjugacy in special monoids, J. Algebra 143(2) (1991) 487–497. Crossref, Web of Science, Google Scholar
    • 73. L. Zhang, Applying rewriting methods to special monoids, Math. Proc. Cambridge Philos. Soc. 112(3) (1992) 495–505. Crossref, Google Scholar
    • 74. L. Zhang, A short proof of a theorem of Adjan, Proc. Amer. Math. Soc. 116(1) (1992) 1–3. Crossref, Web of Science, Google Scholar
    • 75. L. Zhang, Some properties of finite special string-rewriting systems, J. Symbolic Comput. 14(4) (1992) 359–369. Crossref, Web of Science, Google Scholar
    • 76. H. Zieschang, Über die Nielsensche Kürzungsmethode in freien Produkten mit Amalgam, Invent. Math. 10 (1970) 4–37. Crossref, Google Scholar
    Remember to check out the Most Cited Articles!

    Check out Algebra & Computation books in the Mathematics 2021 catalogue.