The concept of self-similar automata over a changing alphabet and lamplighter groups generated by such automata

DOI10.1016/J.TCS.2013.02.027MaRDI QIDQ390918zbMATH OpenOpenAlexFDO

Authors Adam Woryna

Publication date 9 January 2014

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

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

zbMATH Keywords

lamplighter grouprooted treechanging alphabetgroup generated by an automatontime-varying automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Generators, relations, and presentations of groups (20F05) Algebraic theory of languages and automata (68Q70) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Abstract: Generalizing the idea of self-similar groups defined by Mealy automata, we itroduce the notion of a self-similar automaton and a self-similar group over a changing alphabet. We show that every finitely generated residually-finite group is self-similar over an arbitrary unbounded changing alphabet. We construct some naturally defined self-similar automaton representations over an unbounded changing alphabet for any lamplighter group $KwrmathbbZ$ with an arbitrary finitely generated (finite or infinite) abelian group $K$.

Recommendations

• ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
• Extensions of automorphisms of self-similar groups
• Some solvable automaton groups.
• The concept of duality for automata over a changing alphabet and generation of a free group by such automata
• Lamplighter groups and automata

Cites work

• scientific article; zbMATH DE number 5152179 (Why is no real title available?)
• scientific article; zbMATH DE number 3667062 (Why is no real title available?)
• scientific article; zbMATH DE number 647664 (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, dynamical systems, and groups
• Automatically presented groups.
• Conditions of finiteness in Aleshin-type groups
• Groups generated by 3-state automata over a 2-letter alphabet. II.
• La structure des $p$-groupes de Sylow des groupes symétriques finis
• ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
• 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 question of Atiyah
• Piecewise automatic groups.
• Representations of a free group of rank two by time-varying Mealy automata
• Stabilizers of suites in Alëshin-type groups
• The concept of duality for automata over a changing alphabet and generation of a free group by such automata
• The lamplighter group as a group generated by a 2-state automaton, and its spectrum
• The spectra of lamplighter groups and Cayley machines.
• Theory of Alëshin type groups
• WREATH PRODUCTS AND PERIODIC FACTORABLE GROUPS

Cited in

(11)

• Intransitive self-similar groups
• Affine automorphisms of rooted trees
• 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 lamplighter group of rank two generated by a bireversible automaton
• Some solvable automaton groups.
• The lamplighter group \(\mathbb Z_3 \wr \mathbb Z\) generated by a bireversible automaton
• The classification of abelian groups generated by time-varying automata and by Mealy automata over the binary alphabet
• Extensions of automorphisms of self-similar groups
• ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS

This page was built for publication: The concept of self-similar automata over a changing alphabet and lamplighter groups generated by such automata

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