A Characterization of Those Automata That Structurally Generate Finite Groups

DOI10.1007/978-3-642-54423-1_16MaRDI QIDQ5405038zbMATH OpenOpenAlexFDO

Authors Matthieu Picantin, Ines Klimann

Publication date 31 March 2014

Published in LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.7137

zbMATH Keywords

Mealy automataautomaton groupsfiniteness problem

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Semigroups in automata theory, linguistics, etc. (20M35)

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.

Recommendations

• On finite and Abelian groups generated by finite automata.
• The characterization by automata of certain profinite groups.
• On a class of poly-context-free groups generated by automata
• Finitely generated semiautomatic groups
• Finitely generated semiautomatic groups
• Groups defined by automata
• Finite automata over free groups
• Generic properties in some classes of automaton groups
• On certain automorphism groups of finitely generated groups

Cited in

(7)

• A connected 3-state reversible Mealy automaton cannot generate an infinite Burnside group
• A new hierarchy for automaton semigroups
• TREE-WREATHING APPLIED TO GENERATION OF GROUPS BY FINITE AUTOMATA
• Groups and semigroups defined by colorings of synchronizing automata.
• A connected 3-state reversible Mealy automaton cannot generate an infinite Burnside group
• scientific article; zbMATH DE number 3269885 (Why is no real title available?)
• scientific article; zbMATH DE number 3984586 (Why is no real title available?)

This page was built for publication: A Characterization of Those Automata That Structurally Generate Finite Groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405038)