A characterization of those automata that structurally generate finite groups

Abstract : Antonenko and Russyev independently have shown that any Mealy automaton with no cycles with exit--that is, where every cycle in the underlying directed graph is a sink component--generates a fi- nite (semi)group, regardless of the choice of the production functions. Antonenko has proved that this constitutes a characterization in the non-invertible case and asked for the invertible case, which is proved in this paper.
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal-univ-diderot.archives-ouvertes.fr/hal-00877087
Contributor : Ines Klimann <>
Submitted on : Friday, October 25, 2013 - 9:32:47 PM
Last modification on : Friday, January 4, 2019 - 5:32:57 PM
Long-term archiving on : Monday, January 27, 2014 - 1:40:25 PM

Files

arxiv.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00877087, version 1
  • ARXIV : 1310.7137

Collections

Citation

Ines Klimann, Matthieu Picantin. A characterization of those automata that structurally generate finite groups. 11th Latin American Theoretical INformatics Symposium (LATIN 2014), 2014, Uruguay. pp.180--189. ⟨hal-00877087⟩

Share

Metrics

Record views

264

Files downloads

187