Journal article

Publication year: 2016

Pages: 267-289

Journal: Fundamenta Informaticae

Volume number: 148

Issue number: 3-4

ISSN: 0169-2968

eISSN: 1875-8681

DOI Link: https://doi.org/10.3233/FI-2016-1435

Publisher: SAGE Publications

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 lozenge. A partial word language L' can be transformed into an ordinary language L by using a lozenge-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 Sigma(p)(2) depending on the problem investigated.

Harvard Citation style: Holzer, M., Jakobi, S. and Wendlandt, M. (2016) On the Computational Complexity of Partial Word Automata Problems, Fundamenta Informaticae, 148(3-4), pp. 267-289. https://doi.org/10.3233/FI-2016-1435

APA Citation style: Holzer, M., Jakobi, S., & Wendlandt, M. (2016). On the Computational Complexity of Partial Word Automata Problems. Fundamenta Informaticae. 148(3-4), 267-289. https://doi.org/10.3233/FI-2016-1435