Name
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 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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s11856-020-1972-5 | Israel Journal of Mathematics |
Field | DocType | Volume |
Graph,Discrete mathematics,Triviality,Algebraic structure,Automaton,Invertible matrix,Mathematics,Undecidable problem | Journal | 237 |
Issue | ISSN | Citations |
1 | 0021-2172 | 2 |
PageRank | References | Authors |
0.48 | 10 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniele D'Angeli | 1 | 29 | 7.01 |
| Emanuele Rodaro | 2 | 55 | 15.63 |
| Jan Philipp Wächter | 3 | 3 | 3.57 |