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.68139arXiv1607.07644OpenAlexW2022435967MaRDI QIDQ653339FDOQ653339

Authors: Adam Woryna 

Publication date: 9 January 2012

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

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.

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

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

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)

Cites Work

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

Cited In (8)

• Representations of a free group of rank two by time-varying Mealy automata
• Freeness of automaton groups vs boundary dynamics
• The automaton realization of iterated wreath products of cyclic groups.
• 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.
• On some universal construction of minimal topological generating sets for inverse limits of iterated wreath products of non-abelian finite simple groups
• On groups generated by bi-reversible automata: the two-state case over a changing alphabet
• The classification of abelian groups generated by time-varying automata and by Mealy automata over the binary alphabet

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)