DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2016.44

Connected Reversible Mealy Automata of Prime Size Cannot Generate Infinite Burnside Groups

Authors: Thibault Godin and Ines Klimann

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract

The simplest example of an infinite Burnside group arises in the class of automaton groups. However there is no known example of such a group generated by a reversible Mealy automaton. It has been proved that, for a connected automaton of size at most 3, or when the automaton is not bireversible, the generated group cannot be Burnside infinite. In this paper, we extend these results to automata with bigger stateset, proving that, if a connected reversible automaton has a prime number of states, it cannot generate an infinite Burnside group.

Cite as

Thibault Godin and Ines Klimann. Connected Reversible Mealy Automata of Prime Size Cannot Generate Infinite Burnside Groups. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{godin_et_al:LIPIcs.MFCS.2016.44,
  author =	{Godin, Thibault and Klimann, Ines},
  title =	{{Connected Reversible Mealy Automata of Prime Size Cannot Generate Infinite Burnside Groups}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{44:1--44:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.44},
  URN =		{urn:nbn:de:0030-drops-64570},
  doi =		{10.4230/LIPIcs.MFCS.2016.44},
  annote =	{Keywords: Burnside problem, automaton groups, reversibility, orbit trees}
}

Search Results

Documents authored by Godin, Thibault

Connected Reversible Mealy Automata of Prime Size Cannot Generate Infinite Burnside Groups

Abstract

Cite as

Thanks for your feedback!

Could not send message