On the Computational Complexity of Partial Word Automata Problems

• Autorzy: Holzer M. , Jakobi S. , Wendlandt M.

Identyfikatory

DOI

10.3233/FI-2016-1435

• Języki publikacji: EN

Abstrakty

EN

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 ∑^P₂ depending on the problem investigated.

Słowa kluczowe

EN

computational complexity; machine theory; robots; np-hard problems; formal languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 148, nr 3/4
• Strony: 267--289
• Opis fizyczny: Bibliogr. 15 poz., rys.

Twórcy

autor

Holzer M.

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany

autor

Jakobi S.

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany

autor

Wendlandt M.

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany

Bibliografia

• [1] Amilhastre J, Janssen P, Vilarem MC. FA Minimisation Heuristics for a Class of Finite Languages, Proceedings of the 4th International Workshop on Implementing Automata (O. Boldt, H. Jürgensen, Eds.), vol. 2214 in LNCS, Springer, Potsdam, Germany, 2001. doi: 10.1007/3-540-45526-4_1.
• [2] Balkanski E, Blanchet-Sadri F, Kilgore M, Wyatt BJ. Partial Word DFAs, Proceedings of the 18th International Conference on Implementation and Application of Automata (S. Konstantinidis, Ed.), vol. 7982 in LNCS, Springer, Halifax, Nova Scotia, Canada, 2013, pp. 36–47. doi: 10.1007/978-3-642-39274-0_5.
• [3] Birget JC. Intersection and union of regular languages and state complexity, Inform. Process. Lett., 1992;43:185–190. doi: 10.1016/0020-0190(92)90198-5.
• [4] Björklund H, Martens W. The tractability frontier for NFA minimization, J. Comput. System Sci., 2012;78(1):198–210. doi: 10.1016/j.jcss.2011.03.001.
• [5] Blanchet-Sadri F. Algorithmic Combinatorics on Partial Words, Discrete Mathematics and Its Applications, Chapman and Hall/CRC, 2007. ISBN:1420060929, 9781420060928.
• [6] Blanchet-Sadri F, Goldner K, Shackleton A. Minimal Partial Languages and Automata, Proceedings of the 19th International Conference on Implementation and Application of Automata. M. Holzer, M. Kutrib (Eds.), vol. 8587 in LNCS, Springer, Giessen, Germany, July–August 2014, pp 110-123. doi: 10.1007/978-3-319-08846-4_8.
• [7] Cho S, Huynh DT. The Parallel Complexity of Finite-State Automata Problems, Inform. Comput., 1992; 97(1):1–22. doi: 10.1016/0890-5401(92)90002-W.
• [8] Dassow J, Manea F, Merca s R. Regular languages of partial words, Information Sciences, 2014;268:290–304. doi: 10.1016/j.ins.2013.12.032.
• [9] Fischer MJ, Paterson MS. String-Matching and Other Products, In: Complexity of Computation, R.M. Karp (Ed.), vol. 7, American Mathematical Society, 1974, pp. 113–126.
• [10] Gruber H, Holzer M. Computational Complexity of NFA Minimization for Finite and Unary Languages, Proceedings of the 1st International Conference on Language and Automata Theory and Applications, R. Loos, S.Z. Fazekas, C. Martín-Vide (Eds.), Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona, Spain, 2007.
• [11] Jiang T, Ravikumar B. Minimal NFA problems are hard, SIAM J. Comput., 1993;22(6):1117–1141. doi:10.1137/0222067.
• [12] Jones N. Space-bounded reducibility among combinatorial problems, J. Comput. System Sci., 1975; 11(1):68–85. doi: 10.1016/S0022-0000(75)80050-X.
• [13] Kozen D. Lower bounds for natural proof systems, Proceedings of the 18th Annual Symposium on Foundations of Computer Science, 1977. doi: 10.1109/SFCS.1977.16.
• [14] Meyer AR, Stockmeyer LJ. The equivalence problem for regular expressions with squaring requires exponential time, Proceedings of the 13th Annual Symposium on Switching and Automata Theory, IEEE Society Press, 1972. doi: 10.1109/SWAT.1972.29.
• [15] Stockmeyer LJ, Meyer AR. Word Problems Requiring Exponential Time, Proceedings of the 5th Symposium on Theory of Computing, 1973. doi: 10.1145/800125.804029.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).