Automata and square complexes. (Q2487750)

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.