Document Open Access Logo

Streaming Word Problems

Authors Markus Lohrey , Lukas Lück

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.72.pdf
  • Filesize: 0.71 MB
  • 15 pages

Document Identifiers

Author Details

Markus Lohrey
  • Universität Siegen, Germany
Lukas Lück
  • Universität Siegen, Germany

Funding

  • Lohrey, Markus: Funded by DFG project LO 748/12-1.

Cite As Get BibTex

Markus Lohrey and Lukas Lück. Streaming Word Problems. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 72:1-72:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.72

Abstract

We study deterministic and randomized streaming algorithms for word problems of finitely generated groups. For finitely generated linear groups, metabelian groups and free solvable groups we show the existence of randomized streaming algorithms with logarithmic space complexity for their word problems. We also show that the class of finitely generated groups with a logspace randomized streaming algorithm for the word problem is closed under several group theoretical constructions: finite extensions, direct products, free products and wreath products by free abelian groups. We contrast these results with several lower bound. An example of a finitely presented group, where the word problem has only a linear space randomized streaming algorithm, is Thompson’s group F.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • word problems for groups
  • streaming algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58(1):137-147, 1999. URL: https://doi.org/10.1006/jcss.1997.1545.
  2. Anatolij W. Anissimov and Franz D. Seifert. Zur algebraischen Charakteristik der durch kontext-freie Sprachen definierten Gruppen. Elektronische Informationsverarbeitung und Kybernetik, 11(10-12):695-702, 1975. Google Scholar
  3. Vikraman Arvind, Partha Mukhopadhyay, and Srikanth Srinivasan. New results on noncommutative and commutative polynomial identity testing. Computational Complexity, 19(4):521-558, 2010. URL: https://doi.org/10.1007/s00037-010-0299-8.
  4. Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, and Girish Varma. Streaming algorithms for language recognition problems. Theoretical Computer Science, 494:13-23, 2013. URL: https://doi.org/10.1016/j.tcs.2012.12.028.
  5. Laurent Bartholdi. The growth of Grigorchuk’s torsion group. International Mathematics Research Notices, 20:1049-1054, 1998. URL: https://doi.org/10.1155/S1073792898000622.
  6. Laurent Bartholdi. Lower bounds on the growth of a group acting on the binary rooted tree. International Journal of Algebra and Computation, 11(01):73-88, 2001. URL: https://doi.org/10.1142/S0218196701000395.
  7. Gabriel Bathie and Tatiana Starikovskaya. Property testing of regular languages with applications to streaming property testing of visibly pushdown languages. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, volume 198 of LIPIcs, pages 119:1-119:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.119.
  8. John W. Cannon, William J. Floyd, and Walter R. Parry. Introductory notes on Richard Thompson’s groups. L'Enseignement Mathématique, 42(3):215-256, 1996. Google Scholar
  9. Pierre de la Harpe. Topics in Geometric Group Theory. University of Chicago Press, 2000. Google Scholar
  10. Max Dehn. Über unendliche diskontinuierliche Gruppen. Mathematische Annalen, 71:116-144, 1911. In German. URL: https://doi.org/10.1007/BF01456932.
  11. Nathanaël Fijalkow. The online space complexity of probabilistic languages. In Proceedings of the International Symposium on Logical Foundations of Computer Science, LFCS 2016, volume 9537 of Lecture Notes in Computer Science, pages 106-116. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-27683-0_8.
  12. Nathanaël François, Frédéric Magniez, Michel de Rougemont, and Olivier Serre. Streaming property testing of visibly pushdown languages. In Proceedings of the 24th Annual European Symposium on Algorithms, ESA 2016, volume 57 of LIPIcs, pages 43:1-43:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.43.
  13. William Timothy Gowers and Emanuele Viola. Interleaved group products. SIAM Journal on Computing, 48(2):554-580, 2019. URL: https://doi.org/10.1137/17M1126783.
  14. Rostislav I. Grigorchuk. Burnside’s problem on periodic groups. Functional Analysis and Its Applications, 14:41-43, 1980. URL: https://doi.org/10.1007/BF01078416.
  15. Rostislav I. Grigorchuk. On the gap conjecture concerning group growth. Bulletin of Mathematical Sciences, 4(1):113-128, 2014. URL: https://doi.org/10.1007/s13373-012-0029-4.
  16. Mikhail Gromov. Groups of polynomial growth and expanding maps. Publications Mathématiques de L’Institut des Hautes Scientifiques, 53:53-78, 1981. URL: https://doi.org/10.1007/BF02698687.
  17. Victor S. Guba and Mark V. Sapir. On subgroups of the R. Thompson group F and other diagram groups. Matematicheskii Sbornik, 190(8):3-60, 1999. URL: https://doi.org/10.1070/SM1999v190n08ABEH000419.
  18. Derek F. Holt, Sarah Rees, and Claas E. Röver. Groups, Languages and Automata, volume 88 of London Mathematical Society Student Texts. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781316588246.
  19. Richard M. Karp. Some bounds on the storage requirements of sequential machines and Turing machines. Journal of the Association for Computing Machinery, 14(3):478-489, 1967. URL: https://doi.org/10.1145/321406.321410.
  20. Daniel König and Markus Lohrey. Evaluation of circuits over nilpotent and polycyclic groups. Algorithmica, 80(5):1459-1492, 2018. URL: https://doi.org/10.1007/s00453-017-0343-z.
  21. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997. URL: https://doi.org/10.1017/CBO9780511574948.
  22. Jörg Lehnert and Pascal Schweitzer. The co-word problem for the Higman-Thompson group is context-free. Bulletin of the London Mathematical Society, 39(2):235-241, February 2007. URL: https://doi.org/10.1112/blms/bdl043.
  23. Richard J. Lipton and Yechezkel Zalcstein. Word problems solvable in logspace. Journal of the Association for Computing Machinery, 24(3):522-526, 1977. URL: https://doi.org/10.1145/322017.322031.
  24. Markus Lohrey. Decidability and complexity in automatic monoids. International Journal of Foundations of Computer Science, 16(4):707-722, 2005. URL: https://doi.org/10.1142/S0129054105003248.
  25. Markus Lohrey and Lukas Lück. Streaming word problems. CoRR, abs/2202.04060, 2022. URL: https://doi.org/10.48550/ARXIV.2202.04060.
  26. Frédéric Magniez, Claire Mathieu, and Ashwin Nayak. Recognizing well-parenthesized expressions in the streaming model. SIAM Journal on Computing, 43(6):1880-1905, 2014. URL: https://doi.org/10.1137/130926122.
  27. Wilhelm Magnus. On a theorem of Marshall Hall. Annals of Mathematics. Second Series, 40:764-768, 1939. URL: https://doi.org/10.2307/1968892.
  28. Avinoam Mann. How Groups Grow. London Mathematical Society Lecture Note Series. Cambridge University Press, 2011. URL: https://doi.org/10.1017/CBO9781139095129.
  29. Charles F Miller III. Decision problems for groups - survey and reflections. In G. Baumslag and Charles F Miller III, editors, Algorithms and classification in combinatorial group theory, pages 1-59. Springer, 1992. URL: https://doi.org/10.1007/978-1-4613-9730-4_1.
  30. John Milnor. Growth of finitely generated solvable groups. Journal of Differential Geometry, 2(4):447-449, 1968. URL: https://doi.org/10.4310/jdg/1214428659.
  31. David E. Muller and Paul E. Schupp. Groups, the theory of ends, and context-free languages. Journal of Computer and System Sciences, 26:295-310, 1983. URL: https://doi.org/10.1016/0022-0000(83)90003-X.
  32. Alexei Myasnikov, Vitaly Roman'kov, Alexander Ushakov, and AnatolyVershik. The word and geodesic problems in free solvable groups. Transactions of the American Mathematical Society, 362(9):4655-4682, 2010. URL: https://doi.org/10.1090/S0002-9947-10-04959-7.
  33. Azaria Paz. Introduction to Probabilistic Automata. Academic Press, 1971. URL: https://doi.org/10.1016/C2013-0-11297-4.
  34. Michael O. Rabin. Probabilistic automata. Information and Control, 6(3):230-245, 1963. URL: https://doi.org/10.1016/S0019-9958(63)90290-0.
  35. Jeffrey Shallit and Yuri Breitbart. Automaticity I: properties of a measure of descriptional complexity. Journal of Computer and System Sciences, 53(1):10-25, 1996. URL: https://doi.org/10.1006/jcss.1996.0046.
  36. Hans-Ulrich Simon. Word problems for groups and contextfree recognition. In Proceedings of Fundamentals of Computation Theory, FCT 1979, pages 417-422. Akademie-Verlag, 1979. Google Scholar
  37. Jacques Tits. Free subgroups in linear groups. Journal of Algebra, 20:250-270, 1972. URL: https://doi.org/10.1016/0021-8693(72)90058-0.
  38. Alexander Ushakov. Algorithmic theory of free solvable groups: Randomized computations. Journal of Algebra, 407:178-200, 2014. URL: https://doi.org/10.1016/j.jalgebra.2014.02.014.
  39. Stephan Waack. The parallel complexity of some constructions in combinatorial group theory. Journal of Information Processing and Cybernetics, EIK, 26:265-281, 1990. Google Scholar
  40. Bertram A. F. Wehrfritz. On finitely generated soluble linear groups. Mathematische Zeitschrift, 170:155-167, 1980. URL: https://doi.org/10.1007/BF01214771.
  41. Armin Weiß. A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups. In Algebra and Computer Science, volume 677 of Contemporary Mathematics. American Mathematical Society, 2016. URL: https://doi.org/10.1090/conm/677.
  42. Joseph A. Wolf. Growth of finitely generated solvable groups and curvature of Riemannian manifolds. Journal of Differential Geometry, 2(4):421-446, 1968. URL: https://doi.org/10.4310/jdg/1214428658.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact