Document Open Access Logo

The Power Word Problem

Authors Markus Lohrey, Armin Weiß

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2019.43.pdf
  • Filesize: 0.52 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • word problem
  • compressed word problem
  • free groups

Metrics

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

Abstract

In this work we introduce a new succinct variant of the word problem in a finitely generated group G, which we call the power word problem: the input word may contain powers p^x, where p is a finite word over generators of G and x is a binary encoded integer. The power word problem is a restriction of the compressed word problem, where the input word is represented by a straight-line program (i.e., an algebraic circuit over G). The main result of the paper states that the power word problem for a finitely generated free group F is AC^0-Turing-reducible to the word problem for F. Moreover, the following hardness result is shown: For a wreath product G Wr Z, where G is either free of rank at least two or finite non-solvable, the power word problem is complete for coNP. This contrasts with the situation where G is abelian: then the power word problem is shown to be in TC^0.

Cite As Get BibTex

Markus Lohrey and Armin Weiß. The Power Word Problem. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.43

Author Details

Markus Lohrey
  • Universität Siegen, Germany
Armin Weiß
  • Universität Stuttgart, Germany

Funding

  • Lohrey, Markus: Funded by DFG project LO 748/12-1.
  • Weiß, Armin: Funded by DFG project DI 435/7-1.

Acknowledgements

We thank Laurent Bartholdi for pointing out the result [Bartholdi et al, 2003, Theorem 6.6] on the bound of the order of elements in the Grigorchuk group, which allowed us to establish Theorem 10.

References

  1. Eric Allender, Nikhil Balaji, and Samir Datta. Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs. In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014, Part II, volume 8635 of Lecture Notes in Computer Science, pages 13-24. Springer-Verlag, 2014. URL: https://doi.org/10.1007/978-3-662-44465-8_2.
  2. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. Google Scholar
  3. David A. Mix Barrington. Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹. In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 1-5. ACM, 1986. URL: https://doi.org/10.1145/12130.12131.
  4. David A. Mix Barrington. Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹. Journal of Computer and System Sciences, 38(1):150-164, 1989. URL: https://doi.org/10.1016/0022-0000(89)90037-8.
  5. Laurent Bartholdi, Rostislav I. Grigorchuk, and Zoran Šuniḱ. Branch groups. In Handbook of algebra, Vol. 3, pages 989-1112. Elsevier/North-Holland, Amsterdam, 2003. URL: https://doi.org/10.1016/S1570-7954(03)80078-5.
  6. Martin Beaudry, Pierre McKenzie, Pierre Péladeau, and Denis Thérien. Finite Monoids: From Word to Circuit Evaluation. SIAM Journal on Computing, 26(1):138-152, 1997. Google Scholar
  7. Ron Book and Friedrich Otto. String-Rewriting Systems. Springer-Verlag, 1993. Google Scholar
  8. William W. Boone. The word problem. Annals of Mathematics, 70(2):207-265, 1959. Google Scholar
  9. Max Dehn. Ueber unendliche diskontinuierliche Gruppen. Mathematische Annalen, 71:116-144, 1911. Google Scholar
  10. Nathan J. Fine and Herbert S. Wilf. Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society, 16:109-114, 1965. Google Scholar
  11. Esther Galby, Joël Ouaknine, and James Worrell. On Matrix Powering in Low Dimensions. In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, volume 30 of LIPIcs, pages 329-340. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.STACS.2015.329.
  12. Moses Ganardi, Daniel König, Markus Lohrey, and Georg Zetzsche. Knapsack Problems for Wreath Products. In Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, volume 96 of LIPIcs, pages 32:1-32:13. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018. URL: http://www.dagstuhl.de/dagpub/978-3-95977-062-0.
  13. Max Garzon and Yechezkel Zalcstein. The complexity of Grigorchuk groups with application to cryptography. Theoretical Computer Science, 88(1):83-98, 1991. Google Scholar
  14. Guoqiang Ge. Testing Equalities of Multiplicative Representations in Polynomial Time (Extended Abstract). In Proceedings of the 34th Annual Symposium on Foundations of Computer Science, FOCS 1993, pages 422-426. IEEE Computer Society, 1993. Google Scholar
  15. Rostislaw I. Grigorchuk. Burnside’s problem on periodic groups. Functional Analysis and Its Applications, 14:41-43, 1980. Google Scholar
  16. Yuri Gurevich and Paul Schupp. Membership problem for the modular group. SIAM Journal on Computing, 37:425-459, 2007. Google Scholar
  17. Derek Holt. Word-hyperbolic groups have real-time word problem. International Journal of Algebra and Computation, 10:221-227, 200. Google Scholar
  18. Derek Holt, Markus Lohrey, and Saul Schleimer. Compressed Decision Problems in Hyperbolic Groups. In Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, volume 126 of LIPIcs, pages 37:1-37:16. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.37.
  19. Matthias Jantzen. Confluent String Rewriting, volume 14 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, 1988. Google Scholar
  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. Daniel König and Markus Lohrey. Parallel identity testing for skew circuits with big powers and applications. International Journal of Algebra and Computation, 28(6):979-1004, 2018. URL: https://doi.org/10.1142/S0218196718500431.
  22. Richard J. Lipton and Yechezkel Zalcstein. Word Problems Solvable in Logspace. Journal of the ACM, 24:522-526, 1977. Google Scholar
  23. Markus Lohrey. Decidability and complexity in automatic monoids. International Journal of Foundations of Computer Science, 16(4):707-722, 2005. Google Scholar
  24. Markus Lohrey. Word Problems and Membership Problems on Compressed Words. SIAM Journal on Computing, 35(5):1210-1240, 2006. URL: https://doi.org/10.1137/S0097539704445950.
  25. Markus Lohrey. The Compressed Word Problem for Groups. Springer Briefs in Mathematics. Springer-Verlag, 2014. URL: https://doi.org/10.1007/978-1-4939-0748-9.
  26. Markus Lohrey and Saul Schleimer. Efficient computation in groups via compression. In Proceedings of the 2nd International Symposium on Computer Science in Russia, CSR 2007, volume 4649 of Lecture Notes in Computer Science, pages 249-258. Springer-Verlag, 2007. Google Scholar
  27. Markus Lohrey and Armin Weiß. The power word problem. CoRR, abs/1904.08343, 2019. URL: https://arxiv.org/abs/1904.08343.
  28. Markus Lohrey and Georg Zetzsche. Knapsack in Graph Groups. Theory of Computing Systems, 62(1):192-246, 2018. URL: https://doi.org/10.1007/s00224-017-9808-3.
  29. M. Lothaire. Combinatorics on Words, volume 17 of Encyclopedia of Mathematics and Its Applications. Addison-Wesley, 1983. Reprinted by Cambridge University Press, 1997. Google Scholar
  30. Alexei Miasnikov, Svetla Vassileva, and Armin Weiß. The Conjugacy Problem in Free Solvable Groups and Wreath Products of Abelian Groups is in TC⁰. Theory of Computing Systems, 63(4):809-832, 2018. URL: https://doi.org/10.1007/s00224-018-9849-2.
  31. Alexei Myasnikov, Andrey Nikolaev, and Alexander Ushakov. Knapsack Problems in Groups. Mathematics of Computation, 84(292):987-1016, 2015. Google Scholar
  32. Alexei Myasnikov, Alexander Ushakov, and Won Dong-Wook. Power Circuits, exponential Algebra, and Time Complexity. International Journal of Algebra and Computation, 22(6):3-53, 2012. Google Scholar
  33. Alexei Myasnikov and Armin Weiß. TC⁰ circuits for algorithmic problems in nilpotent groups. In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, volume 83 of LIPIcs, pages 23:1-23:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.23.
  34. Pyotr S. Novikov. On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. Steklov, pages 1-143, 1955. In Russian. Google Scholar
  35. David Robinson. Parallel Algorithms for Group Word Problems. PhD thesis, University of California, San Diego, 1993. Google Scholar
  36. Heribert Vollmer. Introduction to Circuit Complexity. Springer-Verlag, 1999. Google Scholar
  37. Stephan Waack. The parallel complexity of some constructions in combinatorial group theory. Journal of Information Processing and Cybernetics, 26(5-6):265-281, 1990. Google Scholar
  38. Armin Weiß. On the Complexity of Conjugacy in Amalgamated Products and HNN Extensions. Dissertation, Institut für Formale Methoden der Informatik, Universität Stuttgart, 2015. Google Scholar
  39. 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, pages 185-212. American Mathematical Society, 2016. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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