The concept of duality for automata over a changing alphabet and generation of a free group by such automata

DOI10.1016/J.TCS.2011.08.017zbMATH Open1230.68139OpenAlexW2022435967MaRDI QIDQ653339FDOQ653339

Authors Adam Woryna

Publication date 9 January 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

2-state automatonautomaton over a changing alphabetMealy-type automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free nonabelian groups (20E05) Algebraic theory of languages and automata (68Q70)

Abstract: In the paper, we deal with the notion of an automaton over a changing alphabet, which generalizes the concept of a Mealy-type automaton. We modify the methods based on the idea of a dual automaton and its action used by B. Steinberg et al. (2011) and M. Vorobets and Ya. Vorobets (2007,2010) and adapt them to automata over a changing alphabet. We show that this modification provides some naturally defined automaton representations of a free nonabelian group by a 2-state automaton over a changing alphabet.

Recommendations

• On groups generated by bi-reversible automata: the two-state case over a changing alphabet
• Automata over a binary alphabet generating free groups of even rank.
• On a free group of transformations defined by an automaton.
• Representations of a free group of rank two by time-varying Mealy automata
• Finite automaton actions of free groups

Cites work

• scientific article; zbMATH DE number 5152179 (Why is no real title available?)
• scientific article; zbMATH DE number 3906731 (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?)
• Algebraic and structural automata theory. Transl. of algebraiczna i structuralna teoria automatów (PWN, Warsaw, 1985)
• Automata and square complexes.
• Automata generating free products of groups of order 2.
• Automata over a binary alphabet generating free groups of even rank.
• Automata, dynamical systems, and groups
• Automatically presented groups.
• Automaton semigroups
• Commensurators of groups and reversible automata
• Free group of infinite unitriangular matrices
• ON GENERATION OF WREATH PRODUCTS OF CYCLIC GROUPS BY TWO STATE TIME VARYING MEALY AUTOMATA
• On a free group of transformations defined by an automaton.
• On a series of finite automata defining free transformation groups.
• Piecewise automatic groups.
• Representations of a free group of rank two by time-varying Mealy automata
• The Generation of GL(n, Z) by Finite State Automata
• The complexity of Grigorchuk groups with application to cryptography
• The generalized dihedral groups \(\text{Dih}(\mathbb{Z}^n)\) as groups generated by time-varying automata.
• The smallest Mealy automaton of intermediate growth.

Cited in

(8)

• On some universal construction of minimal topological generating sets for inverse limits of iterated wreath products of non-abelian finite simple groups
• The classification of abelian groups generated by time-varying automata and by Mealy automata over the binary alphabet
• The concept of self-similar automata over a changing alphabet and lamplighter groups generated by such automata
• The characterization by automata of certain profinite groups.
• Freeness of automaton groups vs boundary dynamics
• On groups generated by bi-reversible automata: the two-state case over a changing alphabet
• Representations of a free group of rank two by time-varying Mealy automata
• The automaton realization of iterated wreath products of cyclic groups.

This page was built for publication: The concept of duality for automata over a changing alphabet and generation of a free group by such automata

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