Affiliations: Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany. {holzer,sebastian.jakobi,matthias.wendlandt}@informatik.uni-giessen.de
Correspondence:
[*]
Address for correspondence: Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany
Abstract: We consider the computational complexity of problems related to partial word automata. Roughly speaking, a partial word is a word in which some positions are unspecified and a partial word automaton is a finite automaton that accepts a partial word language—here the unspecified positions in the word are represented by a “hole” symbol ⋄. A partial word language L′ can be transformed into an ordinary language L by using a ⋄-substitution. In particular, we investigate the complexity of the compression or minimization problem for partial word automata, which is known to be NP-hard. We improve on the previously known complexity on this problem, by showing PSPACE-completeness. In fact, it turns out that almost all problems related to partial word automata, such as, e.g., equivalence and universality, are already PSPACE-complete. Moreover, we also study these problems under the further restriction that the involved automata accept only finite languages. In this case, the complexities of the studied problems drop from PSPACE-completeness down to coNP-hardness and containment in ∑2P depending on the problem investigated.
