On the complexity of the word problem for automaton semigroups and automaton groups

Akhavi, 2012, On the finiteness problem for automaton (semi)groups, Internat. J. Algebra Comput., 22, 1, 10.1142/S021819671250052X Bondarenko, 2012, Growth of Schreier graphs of automaton groups, Math. Ann., 354, 765, 10.1007/s00208-011-0757-x Bondarenko, 2014, The word problem in Hanoi Towers groups, Algebra Discrete Math., 17, 248 Brough, 2015, Automaton semigroup constructions, Semigroup Forum, 90, 763, 10.1007/s00233-014-9632-x Brough, 2017, Automaton semigroups: new construction results and examples of non-automaton semigroups, Theoret. Comput. Sci., 674, 1, 10.1016/j.tcs.2017.02.003 Cain, 2009, Automaton semigroups, Theoret. Comput. Sci., 410, 5022, 10.1016/j.tcs.2009.07.054 D'Angeli, 2014, Groups and semigroups defined by colorings of synchronizing automata, Internat. J. Algebra Comput., 24, 773, 10.1142/S0218196714500337 D'Angeli, 2015, A geometric approach to (semi)-groups defined by automata via dual transducers, Geom. Dedicata, 174, 375, 10.1007/s10711-014-0024-x D'Angeli, 2016, Freeness of automaton groups vs boundary dynamics, J. Algebra, 462, 115, 10.1016/j.jalgebra.2016.05.015 Gillibert, 2014, The finiteness problem for automaton semigroups is undecidable, Internat. J. Algebra Comput., 24, 1, 10.1142/S0218196714500015 Godin, 2015, On torsion-free semigroups generated by invertible reversible Mealy automata, vol. 8977, 328 Grigorchuk, 2008, Groups of intermediate growth: an introduction, Enseign. Math. (2), 54, 1 Howie, 1995, Fundamentals of Semigroup Theory Immerman, 1988, Nondeterministic space is closed under complementation, SIAM J. Comput., 17, 935, 10.1137/0217058 Kozen, 1977, Lower bounds for natural proof systems, 254 Nekrashevych, 2005, Self-Similar Groups, vol. 117 Nekrashevych, 2006, Self-similar inverse semigroups and Smale spaces, Internat. J. Algebra Comput., 16, 849, 10.1142/S0218196706003153 Olijnyk, 2010, Inverse semigroups of partial automaton permutations, Internat. J. Algebra Comput., 20, 923, 10.1142/S0218196710005960 Papadimitriou, 1994 Petrich, 1984, Inverse Semigroups Picantin Savitch, 1970, Relationships between nondeterministic and deterministic tape complexities, J. Comput. System Sci., 4, 177, 10.1016/S0022-0000(70)80006-X Seiferas, 1973, Refinements of the nondeterministic time and space hierarchies, 130 Steinberg, 2015, On some algorithmic properties of finite state automorphisms of rooted trees, vol. 633, 115 Szelepcsényi, 1988, The method of forced enumeration for nondeterministic automata, Acta Inform., 26, 279, 10.1007/BF00299636