2017/12/31 by Daniele D'Angeli, Daniele D’Angeli, Emanuele Rodaro +1 · 9 citations
Computer Science · Mathematics · #Automaton #Büchi automaton #Cellular Automata and Applications #Decidability #Deterministic automaton #Geometric and Algebraic Topology #Invertible matrix #Reversible cellular automaton #Semigroup #Two-way deterministic finite automaton #Undecidable problem #acm:08A99 #acm:20A99 #acm:20E08 #acm:20F05 #acm:20F10 #acm:20M05 #acm:20M30 #cs.FL #math.GR #msc:08A99 #msc:20A99 #msc:20E08 #msc:20F05 #msc:20F10 #msc:20M05 #msc:20M30 #semigroups and automata theory
paper · pdf · doi:10.1007/s11856-020-1972-5
published in Israel Journal of Mathematics 237(1), 15-52 (Hebrew University of Jerusalem)
openalex created_date 2018/01/05 · openalex publication_date 2020/02/12 · arxiv created 2020/04/09 · arxiv updated 2020/04/10 · openalex updated_date 2026/08/05
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. 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. Erratum: Contrary to a statement in a previous version of the paper, our approach does not show that that the freeness problem for automaton semigroups is undecidable. We discuss this in an erratum at the end of the paper.