Automata and Square Complexes

By Yair Glasner, Shahar Mozes. 2003

78 citations recorded by the source corpus.

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 reprove the theorem of Macedońska, Nekrashevych, Sushchansky, on the connection between bi-reversible automata and the commensurator of a regular tree.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/ae4ba134c119b99c20231c8d4a36281b479d3d29

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Classification of groups generated by 3-state automata over a 2-letter alphabet (2008, background): “ed fully invertible (or bi-reversible). Examples of such automata are the automaton2240generatingafree groupwith threegenerators[VV05], Bellaterra automaton [846], and various automata constructed in [GM05], generating free groups of various ranks. We now consider the automaton [846] and its dual mo”
Amenability of linear-activity automaton groups (2009, background): “There are exponential activity growth automaton groups that are isomorphic to the free group (see Glasner and Mozes, 2005; Vorobets and Vorobets, 2007). However, one expects polynomial automaton groups to be smaller. In particular, in contrast with all known finitely generated non-amenable groups, S”