International Journal of Algebra and Computation

In this paper we combine the algebraic properties of Mealy machines generating self-similar groups and the combinatorial properties of the corresponding deterministic finite automata (DFA). In particular, we relate bounded automata to finitely generated synchronizing automata and characterize finite automata groups in terms of nilpotency of the corresponding DFA. Moreover, we present a decidable sufficient condition to have free semigroups in an automaton group. A series of examples and applications is widely discussed, in particular we show a way to color the de Bruijn automata into Mealy automata whose associated semigroups are free, and we present some structural results related to the associated groups.

We discuss a problem posed by Gersten: Is every automatic group which does not contain ℤ × ℤ subgroup, hyperbolic? To study this question, we define the notion of "n-track of length n", which is a structure like ℤ × ℤ, and prove its existence in the non-hyperbolic automatic groups with mild conditions. As an application, we show that if a group acts freely, cellularly, properly discontinuously and cocompactly on a CAT(0) cube complex and its quotient is "weakly special", then the above question is answered affirmatively.

We show that a right-angled Artin group, defined by a graph Γ that has at least three vertices, does not split over an infinite cyclic subgroup if and only if Γ is biconnected. Further, we compute JSJ-decompositions of 1-ended right-angled Artin groups over infinite cyclic subgroups.

If an infinite non-periodic word is uniformly recurrent or is of bounded repetition, then the limit of its periodicity complexity is infinity. Moreover, there are uniformly recurrent words with the periodicity complexity arbitrarily high at infinitely many positions.

The techniques of modules and actions of groups on rooted trees are applied to study the subgroup structure and the lattice subgroup of lamplighter type groups of the form ℒ_n,p = (ℤ/pℤ)ⁿ ≀ ℤ for n ≥ 1 and p prime. We completely characterize scale invariant structures on ℒ_1,2. We determine all points on the boundary of binary tree (on which ℒ_1,p naturally acts in a self-similar manner) with trivial stabilizer. We prove the congruence subgroup property (CSP) and as a consequence show that the profinite completion of ℒ_1,p is a self-similar group generated by finite automaton. We also describe the structure of portraits of elements of ℒ_1,p and and show that ℒ_1,p is not a sofic tree shift group in the terminology of [T. Ceccherini-Silberstein, M. Coornaert, F. Fiorenza and Z. Sunic, Cellular automata between sofic tree shifts, Theor. Comput. Sci.506 (2013) 79–101; A. Penland and Z. Sunic, Sofic tree shifts and self-similar groups, preprint].

Let k be an algebraically closed field, char k ≠ 2, 3, and let X ⊂ ℙ² be an elliptic curve with defining polynomial f. We show that any non-trivial torsion point of order r, determines up to equivalence, a unique minimal matrix Φ_r of size 3r × 3r with linear polynomial entries such that detΦ_r = f^r. We also show that the identity, thought of as the trivial torsion point of order r, determines up to equivalence, a unique minimal matrix Ψ_r of size (3r - 2) × (3r - 2) with linear and quadratic polynomial entries such that detΨ_r = f^r.

We study the complexity of computation in finitely generated free left, right and two-sided adequate semigroups and monoids. We present polynomial time (quadratic in the RAM model of computation) algorithms to solve the word problem and compute normal forms in each of these, and hence to test whether any given identity holds in the classes of left, right and/or two-sided adequate semigroups.

We present a new quasi-isometric invariant for metric spaces that we name asymptotically large depth. For finitely generated groups we show that this invariant implies Yu's property A and is implied by subexponential asymptotic dimension growth.