Abstract: We introduce a new geometric tool for analyzing groups of finite automata. To each finite automaton we associate a square complex. The square complex is covered by a product of two trees iff the automaton is bi-reversible. Using this method we give examples of free groups and of Kazhdan groups which are generated by the different states of one finite (bi-reversible) automaton. We also reproduce the theorem of Macedonska, Nekrashevych, Sushchansky, on the connection between bi-reversible automata and the commensurator of a regular tree.
Recommendations
- Automaton groups and complete square complexes
- Finite automaton actions of free groups
- The lamplighter group \(\mathbb Z_3 \wr \mathbb Z\) generated by a bireversible automaton
- On groups generated by bi-reversible automata: the two-state case over a changing alphabet
- Commensurators of groups and reversible automata
Cites work
- scientific article; zbMATH DE number 5707458 (Why is no real title available?)
- scientific article; zbMATH DE number 52370 (Why is no real title available?)
- An Algebraic Surface with K Ample, (K 2 ) = 9, p g = q = 0
- Arithmétique des algèbres de quaternions
- Automorphism groups of trees acting locally with affine permutations
- Automorphisms of one-rooted trees: growth, circuit structure, and acyclicity.
- Groups acting on \(\text{CAT}(0)\) cube complexes
- Lattices in product of trees
- On closures of orbits and arithmetic of quaternions
- Superrigidity for the commensurability group of tree lattices
- The Generation of GL(n, Z) by Finite State Automata
- The lamplighter group as a group generated by a 2-state automaton, and its spectrum
Cited in
(35)- On the structure theory of partial automaton semigroups
- Freeness of automaton groups vs boundary dynamics
- The concept of duality for automata over a changing alphabet and generation of a free group by such automata
- Arithmetic aspects of self-similar groups.
- Infinite automaton semigroups and groups have infinite orbits
- Free subgroups in groups acting on rooted trees
- Some topics in the dynamics of group actions on rooted trees.
- Self-similar groups and the zig-zag and replacement products of graphs
- Square on Deterministic, Alternating, and Boolean Finite Automata
- Automaton semigroups: the two-state case.
- Combinatorial models of expanding dynamical systems
- Infinite series of quaternionic \(1\)-vertex cube complexes, the doubling construction, and explicit cubical Ramanujan complexes
- Automata generating free products of groups of order 2.
- Automaton groups and complete square complexes
- Boundary dynamics for bireversible and for contracting automaton groups
- Centralizers in \(\tilde A_2\) groups
- On a series of finite automata defining free transformation groups.
- Automaton semigroups
- Orbit automata as a new tool to attack the order problem in automaton groups
- Square on deterministic, alternating, and Boolean finite automata
- Groups generated by 3-state automata over a 2-letter alphabet. II.
- On reversible automata generating lamplighter groups
- Automaton (semi)groups: Wang tilings and Schreier tries
- Automata over a binary alphabet generating free groups of even rank.
- 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
- 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
- Lamplighter groups, bireversible automata, and rational series over finite rings
- Bireversible automata generating lamplighter groups
- On a free group of transformations defined by an automaton.
- Virtual endomorphisms of nilpotent groups.
- On level-transitivity and exponential growth
- Complete square complexes.
- Lifts, derandomization, and diameters of Schreier graphs of Mealy automata
This page was built for publication: Automata and square complexes.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2487750)
