Automata and square complexes.
From MaRDI portal
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.
The authors consider finite automata with output: \(A=(X,Q,\pi,\lambda)\) where \(X\) is a finite alphabet, \(Q\) is a finite set of states, \(\pi\colon X\times Q\to Q\) is the transition function, and \(\lambda\colon X\times Q\to X\) is the output function. To each \(A\) a square complex \(\Sigma(A)\) is associated. It is shown that the automaton \(A\) is bi-reversible if and only if \(\Sigma(A)\) is a VH-complex in which every link is a complete bipartite graph. This is equivalent to the claim that the square complex \(\Sigma(A)\) is covered by a product of two trees. Using this geometric method, the paper provides examples of free groups and Kazhdan groups generated by the states of a finite (bi-reversible) automaton.
Recommendations
Cites work
- 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
- scientific article; zbMATH DE number 5707458 (Why is no real title available?)
- scientific article; zbMATH DE number 52370 (Why is no real title available?)
- 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
(40)- Automaton semigroups
- On level-transitivity and exponential growth
- Arithmetic aspects of self-similar groups.
- Automaton groups and complete square complexes
- Infinite automaton semigroups and groups have infinite orbits
- Self-similar groups and the zig-zag and replacement products of graphs
- Virtual endomorphisms of nilpotent groups.
- On groups generated by bi-reversible automata: the two-state case over a changing alphabet
- Square on deterministic, alternating, and Boolean finite automata
- Complete square complexes.
- The classification of abelian groups generated by time-varying automata and by Mealy automata over the binary alphabet
- Freeness of automaton groups vs boundary dynamics
- On a free group of transformations defined by an automaton.
- Groups generated by 3-state automata over a 2-letter alphabet. II.
- The lamplighter group Z₃ Z generated by a bireversible automaton
- Centralizers in \(\tilde A_2\) groups
- Automaton semigroups: the two-state case.
- Automata over a binary alphabet generating free groups of even rank.
- Automaton (semi)groups: Wang tilings and Schreier tries
- Combinatorial models of expanding dynamical systems
- Square on Deterministic, Alternating, and Boolean Finite Automata
- Boundary dynamics for bireversible and for contracting automaton groups
- Infinite series of quaternionic 1-vertex cube complexes, the doubling construction, and explicit cubical Ramanujan complexes
- Free subgroups in groups acting on rooted trees
- The lamplighter group of rank two generated by a bireversible automaton
- Bireversible automata generating lamplighter groups
- Some topics in the dynamics of group actions on rooted trees.
- The concept of duality for automata over a changing alphabet and generation of a free group by such automata
- Automata generating free products of groups of order 2.
- On reversible automata generating lamplighter groups
- Lifts, derandomization, and diameters of Schreier graphs of Mealy automata
- On groups of reversible automata
- Graphically discrete groups and rigidity
- Amenability of quadratic automaton groups
- The freeness problem for automaton semigroups
- Self-similarity of the generalized Baumslag-Solitar groups
- Lamplighter groups, bireversible automata, and rational series over finite rings
- On the structure theory of partial automaton semigroups
- Orbit automata as a new tool to attack the order problem in automaton groups
- On a series of finite automata defining free transformation groups.
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)
