AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
The Bounded and Precise Word Problems for Presentations of Groups
About this Title
S. V. Ivanov, Department of Mathematics, University of Illinois, 1409 West Green Street, Urbana, IL 61801
Publication: Memoirs of the American Mathematical Society
Publication Year:
2020; Volume 264, Number 1281
ISBNs: 978-1-4704-4143-2 (print); 978-1-4704-5804-1 (online)
DOI: https://doi.org/10.1090/memo/1281
Published electronically: April 10, 2020
Keywords: Presentations of groups,
diagrams,
word problems,
polylogarithmic space,
polygonal curves
MSC: Primary 20F05, 20F06, 20F10, 68Q25, 68U05; Secondary 52B05, 20F65, 68W30.
Table of Contents
Chapters
- 1. Introduction
- 2. Preliminaries
- 3. Proof of Proposition 1.1
- 4. Calculus of Brackets for Group Presentation (1.2)
- 5. Proofs of Theorem 1.2 and Corollary 1.3
- 6. Calculus of Brackets for Group Presentation (1.4)
- 7. Proof of Theorem 1.4
- 8. Minimizing Diagrams over (1.2) and Proofs of Theorem 1.5 and Corollary 1.6
- 9. Construction of Minimal Diagrams over (1.4) and Proof of Theorem 1.7
- 10. Polygonal Curves in the Plane and Proofs of Theorems 1.8, 1.9 and Corollary 1.10
Abstract
We introduce and study the bounded word problem and the precise word problem for groups given by means of generators and defining relations. For example, for every finitely presented group, the bounded word problem is in NP, i.e., it can be solved in nondeterministic polynomial time, and the precise word problem is in PSPACE, i.e., it can be solved in polynomial space. The main technical result of the paper states that, for certain finite presentations of groups, which include the Baumslag-Solitar one-relator groups and free products of cyclic groups, the bounded word problem and the precise word problem can be solved in polylogarithmic space. As consequences of developed techniques that can be described as calculus of brackets, we obtain polylogarithmic space bounds for the computational complexity of the diagram problem for free groups, for the width problem for elements of free groups, and for computation of the area defined by polygonal singular closed curves in the plane. We also obtain polynomial time bounds for these problems.- A. V. Anīsīmov, The group languages, Kibernetika (Kiev) 4 (1971), 18–24 (Russian, with English summary). MR 301981
- Roy Armoni, Amnon Ta-Shma, Avi Wigderson, and Shiyu Zhou, An $O(\log (n)^{4/3})$ space algorithm for $(s,t)$ connectivity in undirected graphs, J. ACM 47 (2000), no. 2, 294–311. MR 1769444, DOI 10.1145/333979.333984
- Sanjeev Arora and Boaz Barak, Computational complexity, Cambridge University Press, Cambridge, 2009. A modern approach. MR 2500087
- David Mix Barrington, Peter Kadau, Klaus-Jörn Lange, and Pierre McKenzie, On the complexity of some problems on groups input as multiplication tables, J. Comput. System Sci. 63 (2001), no. 2, 186–200. Special issue: Complexity 2000 (Florence). MR 1867121, DOI 10.1006/jcss.2001.1764
- J.-C. Birget, A. Yu. Ol′shanskii, E. Rips, and M. V. Sapir, Isoperimetric functions of groups and computational complexity of the word problem, Ann. of Math. (2) 156 (2002), no. 2, 467–518. MR 1933724, DOI 10.2307/3597196
- William W. Boone, Certain simple, unsolvable problems of group theory. V, VI, Nederl. Akad. Wetensch. Proc. Ser. A. 60 = Indag. Math. 19 (1957), 22–27, 227–232. MR 0098776
- William W. Boone, The word problem, Ann. of Math. (2) 70 (1959), 207–265. MR 179237, DOI 10.2307/1970103
- V. V. Borisov, Simple examples of groups with unsolvable word problem, Mat. Zametki 6 (1969), 521–532 (Russian). MR 260851
- Desmond Farrell Cummins, The Dehn function, word problem, and bounded word problem for finitely generated decidable group presentations, ProQuest LLC, Ann Arbor, MI, 2012. Thesis (Ph.D.)–University of Illinois at Urbana-Champaign. MR 3193024
- M. Dehn, Über unendliche diskontinuierliche Gruppen, Math. Ann. 71 (1911), no. 1, 116–144 (German). MR 1511645, DOI 10.1007/BF01456932
- R. I. Grigorchuk and P. F. Kurchanov, On the width of elements in free groups, Ukrain. Mat. Zh. 43 (1991), no. 7-8, 911–918 (Russian, with Ukrainian summary); English transl., Ukrainian Math. J. 43 (1991), no. 7-8, 850–856 (1992). MR 1148843, DOI 10.1007/BF01058681
- Rostislav I. Grigorchuk and Sergei V. Ivanov, On Dehn functions of infinite presentations of groups, Geom. Funct. Anal. 18 (2009), no. 6, 1841–1874. MR 2491693, DOI 10.1007/s00039-009-0712-0
- M. Gromov, Hyperbolic groups, Essays in group theory, Math. Sci. Res. Inst. Publ., vol. 8, Springer, New York, 1987, pp. 75–263. MR 919829, DOI 10.1007/978-1-4613-9586-7_{3}
- G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 6th ed., Oxford University Press, Oxford, 2008. Revised by D. R. Heath-Brown and J. H. Silverman; With a foreword by Andrew Wiles. MR 2445243
- Sergei V. Ivanov, The free Burnside groups of sufficiently large exponents, Internat. J. Algebra Comput. 4 (1994), no. 1-2, ii+308. MR 1283947, DOI 10.1142/S0218196794000026
- Richard J. Lipton and Yechezkel Zalcstein, Word problems solvable in logspace, J. Assoc. Comput. Mach. 24 (1977), no. 3, 522–526. MR 445901, DOI 10.1145/322017.322031
- R. J. Lipton, L. Snyder, and Y. Zalcstein, The complexity of word and isomorphism problems for finite groups (preliminary report), Proceedings of the 1976 Conference on Information Sciences and Systems (Tenth Annual Meeting, Johns Hopkins Univ., Baltimore, Md., 1976) Dept. Electr. Engrg., Johns Hopkins Univ., Baltimore, Md., 1976, pp. 33–35. MR 0480758
- Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Springer-Verlag, Berlin-New York, 1977. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89. MR 0577064
- Wilhelm Magnus, Abraham Karrass, and Donald Solitar, Combinatorial group theory: Presentations of groups in terms of generators and relations, Interscience Publishers [John Wiley & Sons, Inc.], New York-London-Sydney, 1966. MR 0207802
- Apala Majumdar, J. M. Robbins, and Maxim Zyskin, Tangent unit-vector fields: nonabelian homotopy invariants and the Dirichlet energy, C. R. Math. Acad. Sci. Paris 347 (2009), no. 19-20, 1159–1164 (English, with English and French summaries). MR 2566995, DOI 10.1016/j.crma.2009.09.002
- A. Majumdar, J. M. Robbins, and M. Zyskin, Tangent unit-vector fields: nonabelian homotopy invariants and the Dirichlet energy, Acta Math. Sci. Ser. B (Engl. Ed.) 30 (2010), no. 5, 1357–1399. MR 2778607, DOI 10.1016/S0252-9602(10)60131-2
- A. Markoff, On the impossibility of certain algorithms in the theory of associative systems, C. R. (Doklady) Acad. Sci. URSS (N.S.) 55 (1947), 583–586. MR 0020528
- A. Markov, The impossibility of certain algorithms in the theory of associative systems. II, Doklady Akad. Nauk SSSR (N.S.) 58 (1947), 353–356 (Russian). MR 0023208
- Nimrod Megiddo and Uzi Vishkin, On finding a minimum dominating set in a tournament, Theoret. Comput. Sci. 61 (1988), no. 2-3, 307–316. MR 980249, DOI 10.1016/0304-3975(88)90131-4
- P. S. Novikov, On algorithmic unsolvability of the problem of identity, Doklady Akad. Nauk SSSR (N.S.) 85 (1952), 709–712 (Russian). MR 0052436
- P. S. Novikov, Ob algoritmičeskoĭ nerazrešimosti problemy toždestva slov v teorii grupp, Trudy Mat. Inst. Steklov. no. 44, Izdat. Akad. Nauk SSSR, Moscow, 1955 (Russian). MR 0075197
- Ruth Nussinov, George Pieczenik, Jerrold R. Griggs, and Daniel J. Kleitman, Algorithms for loop matchings, SIAM J. Appl. Math. 35 (1978), no. 1, 68–82. MR 496070, DOI 10.1137/0135006
- R. Nussinov and A. B. Jacobson, Fast algorithm for predicting the secondary structure of single stranded RNA, Proc. Natl. Acad. Sci. USA 77(1980), 6309–6313.
- Ruth Nussinov, Bruce Shapiro, Shu Yun Le, and Jacob V. Maizel Jr., Speeding up the dynamic algorithm for planar RNA folding, Math. Biosci. 100 (1990), no. 1, 33–47. MR 1058762, DOI 10.1016/0025-5564(90)90046-2
- A. Yu. Ol′shanskiĭ, Geometry of defining relations in groups, Mathematics and its Applications (Soviet Series), vol. 70, Kluwer Academic Publishers Group, Dordrecht, 1991. Translated from the 1989 Russian original by Yu. A. Bakhturin. MR 1191619
- A. Yu. Ol′shanskiĭ, On calculation of width in free groups, Combinatorial and geometric group theory (Edinburgh, 1993) London Math. Soc. Lecture Note Ser., vol. 204, Cambridge Univ. Press, Cambridge, 1995, pp. 255–258. MR 1320288
- Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285
- Christos H. Papadimitriou and Mihalis Yannakakis, On limited nondeterminism and the complexity of the V-C dimension, J. Comput. System Sci. 53 (1996), no. 2, 161–170. Eighth Annual Structure in Complexity Theory Conference (San Diego, CA, 1993). MR 1418886, DOI 10.1006/jcss.1996.0058
- Emil L. Post, Recursive unsolvability of a problem of Thue, J. Symbolic Logic 12 (1947), 1–11. MR 20527, DOI 10.2307/2267170
- T. R. Riley, Private communication.
- Timothy Riley, Computing area in presentations of the trivial group, Proc. Amer. Math. Soc. 145 (2017), no. 12, 5059–5069. MR 3717937, DOI 10.1090/proc/13625
- Joseph J. Rotman, An introduction to the theory of groups, 4th ed., Graduate Texts in Mathematics, vol. 148, Springer-Verlag, New York, 1995. MR 1307623
- Walter J. Savitch, Relationships between nondeterministic and deterministic tape complexities, J. Comput. System Sci. 4 (1970), 177–192. MR 266702, DOI 10.1016/S0022-0000(70)80006-X
- A. M. Turing, The word problem in semi-groups with cancellation, Ann. of Math. (2) 52 (1950), 491–505. MR 37294, DOI 10.2307/1969481
- M. Zuker and P. Stiegler, Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information, Nucleic Acids Res. 9(1981), 133–148.