Document Open Access Logo

To Infinity and Beyond

Author Ines Klimann

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.131.pdf
  • Filesize: 395 kB
  • 12 pages

Document Identifiers

Author Details

Ines Klimann
  • Univ Paris Diderot, Sorbonne Paris Cité, IRIF, UMR 8243 CNRS, F-75013 Paris, France

Funding

This work was partially supported by the French Agence Nationale pour la Recherche, through the Project MealyM ANR-JS02-012-01.

Cite As Get BibTex

Ines Klimann. To Infinity and Beyond. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 131:1-131:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.131

Abstract

We prove that if a group generated by a bireversible Mealy automaton contains an element of infinite order, then it must have exponential growth. As a direct consequence, no infinite virtually nilpotent group can be generated by a bireversible Mealy automaton.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
  • Theory of computation → Automata over infinite objects
Keywords
  • automaton groups
  • growth of a group
  • exponential growth

Metrics

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

References

  1. L. Bartholdi and A. Erschler. Groups of given intermediate word growth. Ann. Inst. Fourier, 64(5):2003-2036, 2014. Google Scholar
  2. T. Brough and A.J. Cain. Automaton semigroups: New constructions results and examples of non-automaton semigroups. Theoretical Computer Science, 674:1-15, 2017. Google Scholar
  3. C. Drutu and M. Kapovich. Lectures on geometric group theory. URL: https://www.math.ucdavis.edu/~kapovich/EPR/ggt.pdf.
  4. Th. Godin and I. Klimann. On bireversible Mealy automata and the Burnside problem. Theoretical Computer Science, 707:24-35, 2018. Google Scholar
  5. R. Grigorchuk. Degrees of growth of finitely generated groups and the theory of invariant means. Izv. Akad. Nauk SSSR Ser. Mat., 48-5:939-985, 1984. Google Scholar
  6. R. Grigorchuk. Degrees of growth of finitely generated groups, and the theory of invariant means. Mathematics of the USSR-Izvestiya, 25(2):259, 1985. Google Scholar
  7. R. Grigorchuk and I. Pak. Groups of intermediate growth: an introduction. L'Enseignement Mathématique, 54(3-4):251-272, 2008. Google Scholar
  8. R.I. Grigorchuk. On periodic groups generated by finite automata. In 18-th USSR Algebraic Conference, Kishinev, 1985. Google Scholar
  9. I. Klimann. Automaton semigroups: The two-state case. Theor. Comput. Syst. (special issue STACS'13), pages 1-17, 2014. Google Scholar
  10. I. Klimann. On level-transitivity and exponential growth. Semigroup Forum, 95(3):441-447, 2016. Google Scholar
  11. I. Klimann, M. Picantin, and D. Savchuk. A connected 3-state reversible Mealy automaton cannot generate an infinite Burnside group. In DLT' 15, volume 9168 of LNCS, pages 313-325, 2015. Google Scholar
  12. A. Mann. How groups grow, volume 395 of Lecture Note Series. The London Mathematical Society, 2012. Google Scholar
  13. J. Milnor. Advanced problem 5603. MAA Monthly, 75:685-686, 1968. Google Scholar
  14. V. Nekrashevich. Palindromic subshifts and simple periodic groups of intermediate growth. Annals of Mathematics, 187(3):667-719, 2018. Google Scholar
  15. F. Olukoya. The growth rates of automaton groups generated by reset automata. arXiv:1708.07209, 2017. Google Scholar
  16. J.A. Wolf. Growth of finitely generated solvable groups and curvature of riemanniann manifolds. J. Differential Geom., 2(4):421-446, 1968. Google Scholar
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