Automaton (semi)groups: on the undecidability of some problems.

Room FC1 004, DMat-FCUP at 14:30
Friday, 15 December, 2017 (All day)

We consider algorithmic problems for automaton semigroups and automaton groups of the freeness and finiteness kind. We first show that checking whether an automaton group has empty set of positive relations is undecidable. Moreover we prove that the emptyness of the set of positive relations is equivalent to the dynamical property of having all the orbital graphs centred at the non-singular points which are acyclic. We also settle the problem of checking the freeness for the semigroup defined by an automaton group by proving that such problem is undecidable. We also obtain that the finiteness problem for automaton subsemigroups of inverse automaton semigroups is also undecidable. Finally, motivated by the finiteness problem, we consider the problem whether the infiniteness of automaton semigroup is equivalent to the existence of an infinite orbital graph. We conjecture that for automaton groups this is the case. As a partial support to this conjecture, we show that for reversible automaton groups this holds true (In this talk, some results were presented obtained in collaboration with D. D’Angeli and J-P. Wächter).


Emanuele Rodaro


Dep. of Mathematics, Politecnico di Milano.

PDF File: