On computational complexity of set automata. (English) Zbl 1518.68191
Summary: We consider a computational model which is known as set automata. The set automata are one-way finite automata with additional storage – the set. There are two kinds of set automata – deterministic (DSA’s) and nondeterministic (NSA’s). The model was introduced by M. Kutrib et al. [Lect. Notes Comput. Sci. 8633, 303–314 (2014; Zbl 1344.68123); Lect. Notes Comput. Sci. 8614, 282–293 (2014; Zbl 1416.68103)]. It was shown that DSA-recognizable languages look similar to DCFL’s and NSA-recognizable languages look similar to CFL’s.
In this paper, we extend this similarity and prove that languages recognizable by NSA’s form a rational cone, as do CFL’s.
The main topic of this paper is computational complexity: we prove that
In this paper, we extend this similarity and prove that languages recognizable by NSA’s form a rational cone, as do CFL’s.
The main topic of this paper is computational complexity: we prove that
- -
- languages recognizable by DSA’s belong to P and there are P-complete languages among them;
- -
- languages recognizable by NSA’s are in NP and there are NP-complete languages among them;
- -
- the word membership problem is P-complete for DSA’s without \(\varepsilon \)-loops and PSPACE-complete for general DSA’s;
- -
- the emptiness problem is PSPACE-complete for DSA’s.
Keywords:
set automaton; formal language; rational cone; computational complexity; membership problem; emptiness problemReferences:
| [1] | Hopcroft, J.; Ullman, J., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley Publishing Company · Zbl 0426.68001 |
| [2] | Knuth, D.; Morris, J.; Pratt, V., Fast pattern matching in strings, SIAM J. Comput., 6, 323-350 (1977) · Zbl 0372.68005 |
| [3] | Aho, A. V.; Corasick, M. J., Efficient string matching: an aid to bibliographic search, Commun. ACM, 18, 333-340 (1975) · Zbl 0301.68048 |
| [4] | Chomsky, N., On certain formal properties of grammars, Inf. Control, 2, 137-167 (1959) · Zbl 0088.10801 |
| [5] | Ginsburg, S.; Greibach, S. A.; Harrison, M. A., One-way stack automata, J. ACM, 14, 389-418 (1967) · Zbl 0171.14803 |
| [6] | Cherubini, A.; Citrini, C.; Crespi-Reghizzi, S.; Mandrioli, D., QRT FIFO automata, breadth-first grammars and their relations, Theor. Comput. Sci., 85, 171-203 (1991) · Zbl 0745.68069 |
| [7] | Daley, M.; Eramian, M.; McQuillan, I., The bag automaton: a model of nondeterministic storage, J. Autom. Lang. Comb., 13, 185-206 (2008) · Zbl 1191.68380 |
| [8] | Hopcroft, J. E.; Ullman, J. D., An approach to a unified theory of automata, (8th Annual Symposium on Switching and Automata Theory. 8th Annual Symposium on Switching and Automata Theory, Austin, Texas, USA, October 18-20, 1967 (1967), IEEE Computer Society), 140-147 · Zbl 0155.34303 |
| [9] | Kutrib, M.; Malcher, A.; Wendlandt, M., Deterministic set automata, (Shur, A. M.; Volkov, M. V., DLT 2014. DLT 2014, LNCS, vol. 8633 (2014), Springer: Springer Cham), 303-314 · Zbl 1344.68123 |
| [10] | Kutrib, M.; Malcher, A.; Wendlandt, M., Regularity and size of set automata, (Jürgensen, H.; Karhumäki, J.; Okhotin, A., DCFS 2014. DCFS 2014, LNCS, vol. 9118 (2014), Springer: Springer Cham), 282-293 · Zbl 1416.68103 |
| [11] | Kutrib, M.; Malcher, A.; Wendlandt, M., Set automata, Int. J. Found. Comput. Sci., 27, 187-214 (2016) · Zbl 1352.68134 |
| [12] | Lange, K.-J.; Reinhardt, K., Set automata, (Combinatorics, Complexity and Logic; Proceedings of the DMTCS’96 (1996), Springer), 321-329 · Zbl 0914.68117 |
| [13] | Berstel, J., Transductions and Context-free Languages (1979), Teubner · Zbl 0424.68040 |
| [14] | Sipser, M., Introduction to the Theory of Computation (2013), Cengage Learning |
| [15] | Arora, S.; Barak, B., Computational Complexity: A Modern Approach (2009), Cambridge University Press: Cambridge University Press USA · Zbl 1193.68112 |
| [16] | Rubtsov, A.; Vyalyi, M., On computational complexity of set automata, (Charlier, É.; Leroy, J.; Rigo, M., Developments in Language Theory: 21st International Conference, Proceedings. Developments in Language Theory: 21st International Conference, Proceedings, DLT 2017, Liège, Belgium, August 7-11, 2017 (2017), Springer International Publishing: Springer International Publishing Cham), 332-344 · Zbl 1494.68148 |
| [17] | Rubtsov, A.; Vyalyi, M., On emptiness and membership problems for set automata, (Fomin, F. V.; Podolskii, V. V., Computer Science - Theory and Applications (2018), Springer International Publishing: Springer International Publishing Cham), 295-307 · Zbl 1485.68145 |
| [18] | Ladner, R. E., The circuit value problem is log space complete for P, SIGACT News, 7, 18-20 (1975) |
| [19] | Rubtsov, A.; Vyalyi, M., Regular realizability problems and context-free languages, (Shallit, J.; Okhotin, A., DCFS 2015. DCFS 2015, LNCS, vol. 9118 (2015), Springer), 256-267 · Zbl 1432.68244 |
| [20] | Kozen, D., Lower bounds for natural proof systems, (Proceedings of the 18th Annual Symposium on Foundations of Computer Science. Proceedings of the 18th Annual Symposium on Foundations of Computer Science, SFCS ’77 (1977), IEEE Computer Society: IEEE Computer Society Washington, DC, USA), 254-266 |
| [21] | Lange, K.-J.; Rossmanith, P., The emptiness problem for intersections of regular languages, (Havel, I. M.; Koubek, V., Mathematical Foundations of Computer Science 1992: 17th International Symposium, Proceedings. Mathematical Foundations of Computer Science 1992: 17th International Symposium, Proceedings, Prague, Czechoslovakia, August 24-28, 1992 (1992), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 346-354 · Zbl 1493.68191 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
