On groups generated by bi-reversible automata: the two-state case over a changing alphabet

DOI10.1016/J.JCSS.2017.01.004MaRDI QIDQ2396829zbMATH OpenOpenAlexFDO

Authors Adam Woryna

Publication date 26 May 2017

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

automorphism groupfree groupchanging alphabettransducerautomaton over a changing alphabetmealy automatongroup generated by automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Abstract: The notion of an automaton over a changing alphabet $X=(X_i{)}_{igeq1}$ is used to define and study automorphism groups of the tree $X^{\ast }$ of finite words over $X$. The concept of bi-reversibility for Mealy-type automata is extended to automata over a changing alphabet. It is proved that a non-abelian free group can be generated by a two-state bi-reversible automaton over a changing alphabet $X=(X_i{)}_{igeq1}$ if and only if $X$ is unbounded. The characterization of groups generated by a two-state bi-reversible automaton over the sequence of binary alphabets is established.

Recommendations

• The concept of duality for automata over a changing alphabet and generation of a free group by such automata
• Automata over a binary alphabet generating free groups of even rank.
• The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable
• The concept of self-similar automata over a changing alphabet and lamplighter groups generated by such automata
• Automaton semigroups: the two-state case.

Cites work

• scientific article; zbMATH DE number 475380 (Why is no real title available?)
• scientific article; zbMATH DE number 2201548 (Why is no real title available?)
• scientific article; zbMATH DE number 2195483 (Why is no real title available?)
• Automata and square complexes.
• Automata over a binary alphabet generating free groups of even rank.
• Automata, dynamical systems, and groups
• Automaton semigroups: the two-state case.
• Commensurators of groups and reversible automata
• Connected reversible Mealy automata of prime size cannot generate infinite Burnside groups
• Discrete groups of slow subgroup growth
• Freeness of automaton groups vs boundary dynamics
• On a free group of transformations defined by an automaton.
• On a series of finite automata defining free transformation groups.
• Representations of a free group of rank two by time-varying Mealy automata
• Residual properties of free groups. III
• The classification of abelian groups generated by time-varying automata and by Mealy automata over the binary alphabet
• The concept of duality for automata over a changing alphabet and generation of a free group by such automata
• The concept of self-similar automata over a changing alphabet and lamplighter groups generated by such automata
• The lamplighter group \(\mathbb Z_3 \wr \mathbb Z\) generated by a bireversible automaton
• Uncountable universal locally finite groups

Cited in

(4)

• Bireversible automata generating lamplighter groups
• The lamplighter group of rank two generated by a bireversible automaton
• Automata and square complexes.
• The concept of duality for automata over a changing alphabet and generation of a free group by such automata

This page was built for publication: On groups generated by bi-reversible automata: the two-state case over a changing alphabet

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