Automaton semigroups and groups: On the undecidability of problems related to freeness and finiteness
- PDF / 384,027 Bytes
- 38 Pages / 429.408 x 636.768 pts Page_size
- 5 Downloads / 221 Views
AUTOMATON SEMIGROUPS AND GROUPS: ON THE UNDECIDABILITY OF PROBLEMS RELATED TO FREENESS AND FINITENESS
BY
Daniele D’Angeli∗ Universit` a degli Studi Niccol` o Cusano Via Don Carlo Gnocchi 3, 00166 Roma, Italia e-mail: [email protected]
AND
Emanuele Rodaro∗∗ Department of Mathematics, Politecnico di Milano Piazza Leonardo da Vinci 32, 20133 Milano, Italy e-mail: [email protected]
AND
¨chter Jan Philipp Wa Institut f¨ ur Formale Methoden der Informatik (FMI), Universit¨ at Stuttgart Universit¨ atsstraße 38, 70569 Stuttgart, Germany e-mail: [email protected]
∗ The first author was supported by the Austrian Science Fund projects FWF
P24028-N18 and FWF P29355-N35.
∗∗ The second author thanks the project INDAM-GNSAGA.
Received December 20, 2017 and in revised form April 16, 2019
1
2
¨ D. D’ANGELI, E. RODARO AND J. PH. WACHTER
Isr. J. Math.
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 = ½ 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 by the first two authors 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, which negatively solves an open problem by Grigorchuk, Nekrashevych and Sushchansky. In fact, we show 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.
1. Introduction Automaton groups, i.e., groups generated by synchronous Mealy automata, are a quite intriguing class of groups. They have deep connections with many areas of mathematics, from the theory of profinite groups to complex dynamics and theoretical computer science, and they serve as a source of examples or counterexamples for many important group theoretic problems (see, e.g., [41] for an introduction). Despite these connections and the many surprising and interesting consequenc
Data Loading...
