New results on the prefix membership problem for one-relator groups

Dolinka, Igor; Gray, Robert

doi:10.1090/tran/8338

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