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. A detailed listing of the contributions of this paper can be found at the end of this paper.

On the complexity of the word problem for automaton semigroups and automaton groups

D'angeli, Daniele;Rodaro, Emanuele;
2017

Abstract

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. A detailed listing of the contributions of this paper can be found at the end of this paper.
File in questo prodotto:
File Dimensione Formato  
PSPACE word proble automaton semigroups.pdf

Accesso riservato

: Publisher’s version
Dimensione 720.22 kB
Formato Adobe PDF
720.22 kB Adobe PDF   Visualizza/Apri
11311-1036141 Rodaro.pdf

accesso aperto

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 360.34 kB
Formato Adobe PDF
360.34 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11311/1036141
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 8
social impact