On NFAs where all states are final, initial, or both. (English) Zbl 1194.68140
Summary: We examine questions involving nondeterministic finite automata where all states are final, initial, or both initial and final. First, we prove hardness results for the nonuniversality and inequivalence problems for these NFAs. Next, we characterize the languages accepted. Finally, we discuss some state complexity problems involving such automata.
MSC:
| 68Q45 | Formal languages and automata |
References:
| [1] | A, Aho; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley · Zbl 0326.68005 |
| [2] | Birget, J.-C., Partial orders on words, minimal elements of regular languages, and state complexity, Theoret. Comput. Sci., 119, 267-291 (1993), Erratum available at: http://clam.rutgers.edu/ birget/papers.html · Zbl 0786.68071 |
| [3] | Brzozowski, J. A.; Shallit, J.; Xu, Z., Decision problems for convex languages, (Diekert, Volker; Nowotka, Dirk, Developments in Language Theory (13th International Conference, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009. Proceedings). Developments in Language Theory (13th International Conference, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009. Proceedings), Lecture Notes in Computer Science, vol. 5583 (2009), Springer), 247-258, Preprint, 2008, Available at: http://arxiv.org/abs/0808.1928 · Zbl 1234.68201 |
| [4] | Ellul, K.; Krawetz, B.; Shallit, J.; Wang, M.-w., Regular expressions: New results and open problems, J. Automata, Languages, and Combinatorics, 10, 407-437 (2005) · Zbl 1143.68434 |
| [5] | Ershov, Yu. L., On a conjecture of V. A. Uspenskii, Algebra i Logika, 1, 4, 45-48 (1962), (in Russian) · Zbl 0192.07904 |
| [6] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman · Zbl 0411.68039 |
| [7] | Gill, A.; Kou, L., Multiple-entry finite automata, J. Comput. System Sci., 9, 1-19 (1974) · Zbl 0285.94030 |
| [8] | Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley · Zbl 0196.01701 |
| [9] | Jirásková, G., State complexity of some operations on binary regular languages, Theoret. Comput. Sci., 330, 287-298 (2005) · Zbl 1078.68088 |
| [10] | Meyer, A. R.; Fischer, M. J., Economy of description by automata, grammars, and formal systems, (Conference Record 1971 Twelfth Annual Symposium on Switching and Automata Theory (1971), IEEE Computer Society), 188-191 |
| [11] | A.R. Meyer, L.J. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space, in: Proc. 13th Ann. IEEE Symp. on Switching and Automata Theory, 1972, pp. 125-129; A.R. Meyer, L.J. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space, in: Proc. 13th Ann. IEEE Symp. on Switching and Automata Theory, 1972, pp. 125-129 |
| [12] | Moore, F. R., On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata, IEEE Trans. Comput., 20, 1211-1214 (1971) · Zbl 0229.94033 |
| [13] | N. Rampersad, J. Shallit, Z. Xu, The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages. Preprint, July 2009, http://arxiv.org/abs/0907.0159; N. Rampersad, J. Shallit, Z. Xu, The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages. Preprint, July 2009, http://arxiv.org/abs/0907.0159 · Zbl 1279.68171 |
| [14] | W. Sakoda, M. Sipser, Nondeterminism and the size of two-way finite automata, in: Proc. 10th Ann. ACM Symp. on Theory of Computing, 1978, pp. 275-286; W. Sakoda, M. Sipser, Nondeterminism and the size of two-way finite automata, in: Proc. 10th Ann. ACM Symp. on Theory of Computing, 1978, pp. 275-286 · Zbl 1282.68160 |
| [15] | Sipser, M., Introduction to the Theory of Computation (1996), PWS |
| [16] | Veloso, P.; Gill, A., Some remarks on multiple-entry finite automata, J. Comput. System Sci., 18, 304-306 (1979) · Zbl 0402.68046 |
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.
