Title: Automaton Semigroups and Groups: on the Undecidability of Problems Related to Freeness and Finiteness,
Abstract: In this paper, we study algorithmic problems for automaton semigroups and
automaton groups related to freeness and finiteness. In the course of this
study, we also exhibit some connections between the algebraic structure of
automaton (semi)groups and their dynamics on the boundary.
First, we show that it is undecidable to check whether the group generated by
a given invertible automaton has a positive relation, i. e. a relation p = 1
such that p only contains positive generators. Besides its obvious relation to
the freeness of the group, the absence of positive relations has previously
been studied and is connected to the triviality of some stabilizers of the
boundary. We show that the emptiness of the set of positive relations is
equivalent to the dynamical property that all (directed positive) orbital
graphs centered at non-singular points are acyclic. Our approach also works to
show undecidability of the freeness problem for automaton semigroups; in fact,
it shows undecidability of a strengthened version where the input automaton is
complete and invertible.
Gillibert showed that the finiteness problem for automaton semigroups is
undecidable. In the second part of the paper, we show that this undecidability
result also holds if the input is restricted to be bi-reversible and invertible
(but, in general, not complete). As an immediate consequence, we obtain that
the finiteness problem for automaton subsemigroups of semigroups generated by
invertible, yet partial automata, so called automaton-inverse semigroups, is
also undecidable.