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

DOI10.1016/J.JCSS.2017.01.004zbMATH Open1370.68193arXiv1702.00435OpenAlexW2574325846MaRDI QIDQ2396829FDOQ2396829

Authors: Adam Woryna 

Publication date: 26 May 2017

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

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^{*}$ 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.

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Automata and square complexes.
• On a free group of transformations defined by an automaton.
• Automata, dynamical systems, and groups
• Automaton semigroups: the two-state case.
• Automata over a binary alphabet generating free groups of even rank.
• On a series of finite automata defining free transformation groups.
• The Lamplighter Group ℤ₃≀ℤ Generated by a Bireversible Automaton
• The concept of self-similar automata over a changing alphabet and lamplighter groups generated by such automata
• Title not available (Why is that?)
• Representations of a free group of rank two by time-varying Mealy automata
• The concept of duality for automata over a changing alphabet and generation of a free group by such automata
• Title not available (Why is that?)
• Uncountable universal locally finite groups
• Discrete groups of slow subgroup growth
• Commensurators of groups and reversible automata
• Residual properties of free groups. III
• Connected reversible Mealy automata of prime size cannot generate infinite Burnside groups
• Freeness of automaton groups vs boundary dynamics
• The classification of abelian groups generated by time-varying automata and by Mealy automata over the binary alphabet

Cited In (4)

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

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)