2016/11/30 by Daniele D'Angeli, Daniele D’Angeli, Emanuele Rodaro +1 · 1 citation
Computer Science · Mathematics · #Geometric and Algebraic Topology #Natural Language Processing Techniques #acm:20E08 #acm:20F10 #acm:20M05 #acm:20M18 #acm:20M30 #acm:68Q17 #acm:68Q45 #cs.CC #cs.FL #math.GR #msc:20E08 #msc:20F10 #msc:20M05 #msc:20M18 #msc:20M30 #msc:68Q17 #msc:68Q45 #semigroups and automata theory
paper · pdf · doi:10.1016/j.aam.2017.05.008
published as Advances in Applied Mathematics, Volume 90, September 2017, Pages 160-187, ISSN 0196-8858
openalex publication_date 2017/06/26 · arxiv created 2017/06/28 · arxiv updated 2017/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
In this paper, we study the word problem for automaton semigroups and automaton groups from a complexity point of view. As an intermediate concept between automaton semigroups and automaton groups, we introduce automaton-inverse semigroups, which are generated by partial, yet invertible automata. We show that there is an automaton-inverse semigroup and, thus, an automaton semigroup with a PSPACE-complete word problem. We also show that there is an automaton group for which the word problem with a single rational constraint is PSPACE-complete. Additionally, we provide simpler constructions for the uniform word problems of these classes. For the uniform word problem for automaton groups (without rational constraints), we show NL-hardness. Finally, we investigate a question asked by Cain about a better upper bound for the length of a word on which two distinct elements of an automaton semigroup must act differently.