Automata and square complexes.

DOI10.1007/S10711-004-1815-2zbMATH Open1088.20037arXivmath/0306259OpenAlexW2042865580MaRDI QIDQ2487750FDOQ2487750

Authors: Yair Glasner, Shahar Mozes 

Publication date: 8 August 2005

Published in: Geometriae Dedicata (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

finite automatafree groupssquare complexessynchronizing automata

Mathematics Subject Classification ID

Groups acting on trees (20E08) Generators, relations, and presentations of groups (20F05) Geometric group theory (20F65) Dynamical aspects of cellular automata (37B15) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Automorphisms of one-rooted trees: growth, circuit structure, and acyclicity.
• Lattices in product of trees
• The lamplighter group as a group generated by a 2-state automaton, and its spectrum
• Title not available (Why is that?)
• Arithmétique des algèbres de quaternions
• The Generation of GL(n, Z) by Finite State Automata
• Groups acting on \(\text{CAT}(0)\) cube complexes
• An Algebraic Surface with K Ample, (K 2 ) = 9, p g = q = 0
• Superrigidity for the commensurability group of tree lattices
• Automorphism groups of trees acting locally with affine permutations
• On closures of orbits and arithmetic of quaternions
• Title not available (Why is that?)

Cited In (35)

• Freeness of automaton groups vs boundary dynamics
• On the structure theory of partial automaton semigroups
• 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
• Boundary dynamics for bireversible and for contracting automaton groups
• Automata generating free products of groups of order 2.
• Automaton groups and complete square complexes
• Centralizers in \(\tilde A_2\) groups
• On a series of finite automata defining free transformation groups.
• Automaton semigroups
• Square on deterministic, alternating, and Boolean finite automata
• Orbit automata as a new tool to attack the order problem in automaton groups
• 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)