Document Open Access Logo

Rational Subsets of Baumslag-Solitar Groups

Authors Michaël Cadilhac , Dmitry Chistikov , Georg Zetzsche

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.116.pdf
  • Filesize: 0.53 MB
  • 16 pages

Document Identifiers

Author Details

Michaël Cadilhac
  • DePaul University, Chicago, IL, USA
Dmitry Chistikov
  • Centre for Discrete Mathematics and its Applications (DIMAP) & Department of Computer Science, University of Warwick, Coventry, UK
Georg Zetzsche
  • Max Planck Institute for Software Systems (MPI-SWS), Kaiserslautern, Germany

Acknowledgements

The research for this work was carried out in part at the Autobóz Research Camp in 2019 in Firbush, Scotland. The authors are very grateful to Piotr Hofman for comments that led to important insights and to Michael Blondin as well as to all other participants for discussions.

Cite AsGet BibTex

Michaël Cadilhac, Dmitry Chistikov, and Georg Zetzsche. Rational Subsets of Baumslag-Solitar Groups. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 116:1-116:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.116

Abstract

We consider the rational subset membership problem for Baumslag-Solitar groups. These groups form a prominent class in the area of algorithmic group theory, and they were recently identified as an obstacle for understanding the rational subsets of GL(2,ℚ). We show that rational subset membership for Baumslag-Solitar groups BS(1,q) with q ≥ 2 is decidable and PSPACE-complete. To this end, we introduce a word representation of the elements of BS(1,q): their pointed expansion (PE), an annotated q-ary expansion. Seeing subsets of BS(1,q) as word languages, this leads to a natural notion of PE-regular subsets of BS(1,q): these are the subsets of BS(1,q) whose sets of PE are regular languages. Our proof shows that every rational subset of BS(1,q) is PE-regular. Since the class of PE-regular subsets of BS(1,q) is well-equipped with closure properties, we obtain further applications of these results. Our results imply that (i) emptiness of Boolean combinations of rational subsets is decidable, (ii) membership to each fixed rational subset of BS(1,q) is decidable in logarithmic space, and (iii) it is decidable whether a given rational subset is recognizable. In particular, it is decidable whether a given finitely generated subgroup of BS(1,q) has finite index.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Formal languages and automata theory
  • Theory of computation → Models of computation
Keywords
  • Rational subsets
  • Baumslag-Solitar groups
  • decidability
  • regular languages
  • pointed expansion

Metrics

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

Related Versions

References

  1. Nathalie Aubrun and Jarkko Kari. Tiling problems on Baumslag-Solitar groups. In Proceedings of Machines, Computations and Universality 2013 (MCU 2013), pages 35-46, 2013. URL: https://doi.org/10.4204/EPTCS.128.12.
  2. Laurent Bartholdi and Pedro V. Silva. Rational subsets of groups. CoRR, abs/1012.1532, 2010. Chapter 23 of the handbook AutoMathA (to appear). URL: http://arxiv.org/abs/1012.1532.
  3. Gilbert Baumslag and Donald Solitar. Some two-generator one-relator non-Hopfian groups. Bulletin of the American Mathematical Society, 68(3):199-201, 1962. URL: https://doi.org/10.1090/S0002-9904-1962-10745-9.
  4. Galina Aleksandrovna Bazhenova. Rational sets in finitely generated nilpotent groups. Algebra and Logic, 39(4):215-223, 2000. URL: https://doi.org/10.1007/BF02681647.
  5. Jason P. Bell, Kathryn Hare, and Jeffrey Shallit. When is an automatic set an additive basis? Proceedings of the American Mathematical Society, Series B, 5(6):50-63, 2018. URL: https://doi.org/10.1090/bproc/37.
  6. Michèle Benois. Parties rationnelles du groupe libre. CR Acad. Sci. Paris, 269:1188-1190, 1969. Google Scholar
  7. Jean Berstel. Transductions and Context-Free Languages. Teubner, 1979. Google Scholar
  8. Valérie Berthé and Michel Rigo, editors. Combinatorics, automata, and number theory, volume 135 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2010. Google Scholar
  9. Laura Ciobanu and Murray Elder. Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), pages 110:1-110:15, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.110.
  10. Jordi Delgado Rodríguez. Extensions of free groups: algebraic, geometric, and algorithmic aspects. PhD thesis, Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística, 2017. Google Scholar
  11. Volker Diekert, Claudio Gutierrez, and Christian Hagenah. The existential theory of equations with rational constraints in free groups is PSPACE -complete. Information and Computation, 202(2):105-140, 2005. URL: https://doi.org/10.1016/j.ic.2005.04.002.
  12. Volker Diekert, Olga Kharlampovich, Markus Lohrey, and Alexei G. Myasnikov. Algorithmic Problems in Group Theory (Dagstuhl Seminar 19131). Dagstuhl Reports, 9(3):83-110, 2019. URL: https://doi.org/10.4230/DagRep.9.3.83.
  13. Volker Diekert and Jürn Laun. On computing geodesics in Baumslag-Solitar groups. International Journal on Algebra and Computation, 21(1-2):119-145, 2011. URL: https://doi.org/10.1142/S0218196711006108.
  14. Volker Diekert, Alexei G. Myasnikov, and Armin Weiß. Conjugacy in Baumslag’s group, generic case complexity, and division in power circuits. In Proceedings of 11th Latin American Symposium on Theoretical Informatics (LATIN 2014), pages 1-12, 2014. URL: https://doi.org/10.1007/978-3-642-54423-1_1.
  15. Volker Diekert, Igor Potapov, and Pavel Semukhin. Decidability of membership problems for flat rational subsets of GL(2, ℚ) and singular matrices, 2019. URL: http://arxiv.org/abs/1910.02302.
  16. F. A. Dudkin and A. V. Treyer. Knapsack problem for Baumslag–Solitar groups. Siberian Journal of Pure and Applied Mathematics, 18:43-55, 2018. URL: https://doi.org/10.33048/pam.2018.18.404.
  17. Murray Elder. A linear-time algorithm to compute geodesics in solvable Baumslag–Solitar groups. Illinois Journal of Mathematics, 54(1):109-128, 2010. URL: https://doi.org/10.1215/ijm/1299679740.
  18. Murray Elder, Gillian Elston, and Gretchen Ostheimer. On groups that have normal forms computable in logspace. Journal of Algebra, 381:260-281, 2013. URL: https://doi.org/10.1016/j.jalgebra.2013.01.036.
  19. Seymour Ginsburg and Edwin H. Spanier. Bounded regular sets. Proceedings of the American Mathematical Society, 17(5):1043-1049, 1966. URL: https://doi.org/10.2307/2036087.
  20. Oscar H. Ibarra. Reversal-bounded multicounter machines and their decision problems. Journal of the ACM, 25(1):116-133, 1978. URL: https://doi.org/10.1145/322047.322058.
  21. Ilya Kapovich and Alexei Myasnikov. Stallings foldings and subgroups of free groups. Journal of Algebra, 248(2):608-668, 2002. URL: https://doi.org/10.1006/jabr.2001.9033.
  22. Olga Kharlampovich, Laura López, and Alexei Miasnikov. Diophantine problem in some metabelian groups, 2019. URL: http://arxiv.org/abs/1903.10068.
  23. Dexter Kozen. Lower bounds for natural proof systems. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS 1977), pages 254-266, 1977. URL: https://doi.org/10.1109/SFCS.1977.16.
  24. Markus Lohrey. The rational subset membership problem for groups: a survey. In C. M. Campbell, M. R. Quick, E. F. Robertson, and C. M. Roney-Dougal, editors, Groups St Andrews 2013, volume 422 of Lond. Math. S., pages 368-389, Cambridge, United Kingdom, 2016. Cambridge University Press. URL: https://doi.org/10.1017/CBO9781316227343.024.
  25. Markus Lohrey and Géraud Sénizergues. Rational subsets in HNN-extensions and amalgamated products. International Journal on Algebra and Computation, 18(1):111-163, 2008. URL: https://doi.org/10.1142/S021819670800438X.
  26. Markus Lohrey and Georg Zetzsche. Knapsack in metabelian Baumslag-Solitar groups, 2020. URL: http://arxiv.org/abs/2002.03837.
  27. Alexei Myasnikov, Andrey Nikolaev, and Alexander Ushakov. Knapsack problems in groups. Mathematics of Computation, 84:987-1016, 2015. URL: https://doi.org/10.1090/S0025-5718-2014-02880-9.
  28. David Robinson. Parallel Algorithms for Group Word Problems. PhD thesis, Department of Mathematics, University of Califoria, San Diego, 1993. Google Scholar
  29. N. S. Romanovskiĭ. Some algorithmic problems for solvable groups. Algebra and Logic, 13:13-16, 1974. URL: https://doi.org/10.1007/BF01462922.
  30. N. S. Romanovskiĭ. The occurrence problem for extensions of abelian groups by nilpotent groups. Siberian Mathematical Journal, 21:273-276, 1980. URL: https://doi.org/10.1007/BF00968275.
  31. Géraud Sénizergues. On the rational subsets of the free group. Acta Informatica, 33(3):281-296, 1996. URL: https://doi.org/10.1007/s002360050045.
  32. John C Shepherdson. The reduction of two-way automata to one-way automata. IBM Journal of Research and Development, 3(2):198-200, 1959. URL: https://doi.org/10.1147/rd.32.0198.
  33. Pedro V. Silva. Free group languages: Rational versus recognizable. RAIRO - Theoretical Informatics and Applications, 38(1):49-67, 2004. URL: https://doi.org/10.1051/ita:2004003.
  34. Pedro V. Silva. An automata-theoretic approach to the study of fixed points of endomorphisms. In Ventura E. González-Meneses J., Lustig M., editor, Algorithmic and Geometric Topics Around Free Groups and Automorphisms, Advanced Courses in Mathematics - CRM Barcelona, pages 1-42. Birkhäuser, 2017. URL: https://doi.org/10.1007/978-3-319-60940-9_1.
  35. Armin Weiß. On the Complexity of Conjugacy in Amalgamated Products and HNN Extensions. PhD thesis, Institut für Formale Methoden der Informatik, Universität Stuttgart, 2015. URL: https://doi.org/10.18419/opus-3538.
  36. Herbert S. Wilf. A circle-of-lights algorithm for the "money-changing problem". The American Mathematical Monthly, 85(7):562-565, 1978. URL: https://doi.org/10.2307/2320864.
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 Imprint Privacy Contact