New results on the prefix membership problem for one-relator groups
HTML articles powered by AMS MathViewer
- by Igor Dolinka and Robert D. Gray PDF
- Trans. Amer. Math. Soc. 374 (2021), 4309-4358 Request permission
Abstract:
In this paper we prove several results regarding decidability of the membership problem for certain submonoids in amalgamated free products and HNN extensions of groups. These general results are then applied to solve the prefix membership problem for a number of classes of one-relator groups which are low in the Magnus–Moldavanskiĭ hierarchy. Since the prefix membership problem for one-relator groups is intimately related to the word problem for one-relator special inverse monoids in the $E$-unitary case (as discovered in 2001 by Ivanov, Margolis and Meakin), these results yield solutions of the word problem for several new classes of one-relator special inverse monoids. In establishing these results, we introduce a new theory of conservative factorisations of words which provides a link between the prefix membership problem of a one-relator group and the group of units of the corresponding one-relator special inverse monoid. Finally, we exhibit the first example of a one-relator group, defined by a reduced relator word, that has an undecidable prefix membership problem.References
- S. I. Adjan, Defining relations and algorithmic problems for groups and semigroups, Trudy Mat. Inst. Steklov. 85 (1966), 123 (Russian). MR 0204501
- S. I. Adyan and G. U. Oganesyan, On the word and divisibility problems for semigroups with one relation, Mat. Zametki 41 (1987), no. 3, 412–421, 458 (Russian). MR 893370
- L. Bartholdi, P. V. Silva, Rational subsets of groups, Chapter 23 in: Handbook of Automata Theory (ed. J.-É. Pin), to appear, arXiv:1012.1532.
- Michèle Benois, Parties rationnelles du groupe libre, C. R. Acad. Sci. Paris Sér. A-B 269 (1969), A1188–A1190. MR 265496
- M. Bestvina, Questions in geometric group theory, a problem collection. Available online at: http://www.math.utah.edu/~bestvina/eprints/questions-updated.pdf
- Jean-Camille Birget, Stuart W. Margolis, and John C. Meakin, The word problem for inverse monoids presented by one idempotent relator, Theoret. Comput. Sci. 123 (1994), no. 2, 273–289. MR 1256202, DOI 10.1016/0304-3975(92)00063-W
- L. Ciobanu, B. Fine, and G. Rosenberger, The surface group conjecture: cyclically pinched and conjugacy pinched one-relator groups, Results Math. 64 (2013), no. 1-2, 175–184. MR 3095136, DOI 10.1007/s00025-013-0307-9
- M. Dehn, Über unendliche diskontinuierliche Gruppen, Math. Ann. 71 (1911), no. 1, 116–144 (German). MR 1511645, DOI 10.1007/BF01456932
- Benjamin Fine, Gerhard Rosenberger, and Michael Stille, Conjugacy pinched and cyclically pinched one-relator groups, Rev. Mat. Univ. Complut. Madrid 10 (1997), no. 2, 207–227. MR 1605642
- Robert D. Gray, Undecidability of the word problem for one-relator inverse monoids via right-angled Artin subgroups of one-relator groups, Invent. Math. 219 (2020), no. 3, 987–1008. MR 4055182, DOI 10.1007/s00222-019-00920-2
- R. D. Gray, N. Ruškuc, On groups of units of special and one-relator inverse monoids, submitted, arXiv:2103.02995
- Zeph Grunschlag, Algorithms in geometric group theory, ProQuest LLC, Ann Arbor, MI, 1999. Thesis (Ph.D.)–University of California, Berkeley. MR 2699134
- Thomas Herbst, On a subclass of context-free groups, RAIRO Inform. Théor. Appl. 25 (1991), no. 3, 255–272 (English, with French summary). MR 1119044, DOI 10.1051/ita/1991250302551
- Susan Hermiller, Steven Lindblad, and John Meakin, Decision problems for inverse monoids presented by a single sparse relator, Semigroup Forum 81 (2010), no. 1, 128–144. MR 2672175, DOI 10.1007/s00233-010-9247-9
- John E. Hopcroft and Jeffrey D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley Series in Computer Science, Addison-Wesley Publishing Co., Reading, Mass., 1979. MR 645539
- Muhammad Inam, The word problem for some classes of Adian inverse semigroups, Semigroup Forum 95 (2017), no. 1, 192–221. MR 3683939, DOI 10.1007/s00233-017-9890-5
- J. Howie, Personal communication, 2018.
- John M. Howie, Fundamentals of semigroup theory, London Mathematical Society Monographs. New Series, vol. 12, The Clarendon Press, Oxford University Press, New York, 1995. Oxford Science Publications. MR 1455373
- S. V. Ivanov, S. W. Margolis, and J. C. Meakin, On one-relator inverse monoids and one-relator groups, J. Pure Appl. Algebra 159 (2001), no. 1, 83–111. MR 1823508, DOI 10.1016/S0022-4049(00)00075-X
- Arye Juhász, Solution of the membership problem of the prefix monoid in certain one-relator groups, Semigroup Forum 89 (2014), no. 3, 479–490. MR 3274829, DOI 10.1007/s00233-014-9614-z
- Mark Kambites, Pedro V. Silva, and Benjamin Steinberg, On the rational subset problem for groups, J. Algebra 309 (2007), no. 2, 622–639. MR 2303197, DOI 10.1016/j.jalgebra.2006.05.020
- Ilya Kapovich, Richard Weidmann, and Alexei Miasnikov, Foldings, graphs of groups and the membership problem, Internat. J. Algebra Comput. 15 (2005), no. 1, 95–128. MR 2130178, DOI 10.1142/S021819670500213X
- Gérard Lallement, On monoids presented by a single relation, J. Algebra 32 (1974), 370–388. MR 354908, DOI 10.1016/0021-8693(74)90146-X
- Mark V. Lawson, Inverse semigroups, World Scientific Publishing Co., Inc., River Edge, NJ, 1998. The theory of partial symmetries. MR 1694900, DOI 10.1142/9789812816689
- Markus Lohrey, The rational subset membership problem for groups: a survey, Groups St Andrews 2013, London Math. Soc. Lecture Note Ser., vol. 422, Cambridge Univ. Press, Cambridge, 2015, pp. 368–389. MR 3495668
- Markus Lohrey and Benjamin Steinberg, The submonoid and rational subset membership problems for graph groups, J. Algebra 320 (2008), no. 2, 728–755. MR 2422314, DOI 10.1016/j.jalgebra.2007.08.025
- 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
- Wilhelm Magnus, Über diskontinuierliche Gruppen mit einer definierenden Relation. (Der Freiheitssatz), J. Reine Angew. Math. 163 (1930), 141–165 (German). MR 1581238, DOI 10.1515/crll.1930.163.141
- 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
- Stuart W. Margolis and John C. Meakin, Inverse monoids, trees and context-free languages, Trans. Amer. Math. Soc. 335 (1993), no. 1, 259–276. MR 1073775, DOI 10.1090/S0002-9947-1993-1073775-X
- Stuart W. Margolis, John C. Meakin, and Joseph B. Stephen, Some decision problems for inverse monoid presentations, Semigroups and their applications (Chico, Calif., 1986) Reidel, Dordrecht, 1987, pp. 99–110. MR 900650
- Stuart W. Margolis, John Meakin, and Zoran Šuniḱ, Distortion functions and the membership problem for submonoids of groups and monoids, Geometric methods in group theory, Contemp. Math., vol. 372, Amer. Math. Soc., Providence, RI, 2005, pp. 109–129. MR 2139682, DOI 10.1090/conm/372/06879
- James McCool and Paul E. Schupp, On one relator groups and $\textrm {HNN}$ extensions, J. Austral. Math. Soc. 16 (1973), 249–256. Collection of articles dedicated to the memory of Hanna Neumann, II. MR 0338186
- John Meakin, Groups and semigroups: connections and contrasts, Groups St. Andrews 2005. Vol. 2, London Math. Soc. Lecture Note Ser., vol. 340, Cambridge Univ. Press, Cambridge, 2007, pp. 357–400. MR 2331597, DOI 10.1017/CBO9780511721205.002
- D. I. Moldavanskiĭ, Certain subgroups of groups with one defining relation, Sibirsk. Mat. Ž. 8 (1967), 1370–1384 (Russian). MR 0220810
- W. D. Munn, Free inverse semigroups, Proc. London Math. Soc. (3) 29 (1974), 385–404. MR 360881, DOI 10.1112/plms/s3-29.3.385
- F. Otto, Deciding whether a monoid is a free monoid or is a group, Acta Inform. 23 (1986), no. 1, 99–110. MR 845625, DOI 10.1007/BF00268077
- Mario Petrich, Inverse semigroups, Pure and Applied Mathematics (New York), John Wiley & Sons, Inc., New York, 1984. A Wiley-Interscience Publication. MR 752899
- J.-É. Pin, Mathematical foundations of automata theory, manuscript, vi+332 pp., version of March 13, 2019. Available online at: https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf
- H. E. Scheiblich, Free inverse semigroups, Proc. Amer. Math. Soc. 38 (1973), 1–7. MR 310093, DOI 10.1090/S0002-9939-1973-0310093-1
- J. B. Stephen, Presentations of inverse monoids, J. Pure Appl. Algebra 63 (1990), no. 1, 81–112. MR 1037695, DOI 10.1016/0022-4049(90)90057-O
- Louxin Zhang, A short proof of a theorem of Adjan, Proc. Amer. Math. Soc. 116 (1992), no. 1, 1–3. MR 1092933, DOI 10.1090/S0002-9939-1992-1092933-6
Additional Information
- Igor Dolinka
- Affiliation: Department of Mathematics and Informatics, University of Novi Sad, Trg Dositeja Obradovića 4, 21101 Novi Sad, Serbia
- MR Author ID: 621746
- ORCID: 0000-0002-8644-0626
- Email: dockie@dmi.uns.ac.rs
- Robert D. Gray
- Affiliation: School of Mathematics, University of East Anglia, Norwich NR4 7TJ, England, United Kingdom
- MR Author ID: 774787
- Email: Robert.D.Gray@uea.ac.uk
- Received by editor(s): November 29, 2019
- Received by editor(s) in revised form: October 21, 2020
- Published electronically: March 30, 2021
- Additional Notes: The research of the first named author was supported by the Ministry of Education, Science, and Technological Development of the Republic of Serbia through the grant No.174019. The research of the second named author was supported by the EPSRC grant EP/N033353/1 “Special inverse monoids: subgroups, structure, geometry, rewriting systems and the word problem”
- © Copyright 2021 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 374 (2021), 4309-4358
- MSC (2020): Primary 20F10; Secondary 20F05, 20M05, 20M18, 68Q70
- DOI: https://doi.org/10.1090/tran/8338
- MathSciNet review: 4251231