×

State complexity of some operations on binary regular languages. (English) Zbl 1078.68088

Summary: We investigate the state complexity of some operations on binary regular languages. In particular, we consider the concatenation of languages represented by deterministic finite automata, and the reversal and complementation of languages represented by nondeterministic finite automata. We prove that the upper bounds on the state complexity of these operations, which were known to be tight for larger alphabets, are tight also for binary alphabets.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Berman, A. Lingas, On the complexity of regular languages in terms of finite automata, Techn. Report 304, Polish Academy of Sciences, 1977.; P. Berman, A. Lingas, On the complexity of regular languages in terms of finite automata, Techn. Report 304, Polish Academy of Sciences, 1977. · Zbl 0364.68057
[2] Birget, J. C., Intersection and union of regular languages and state complexity, Inform. Process. Lett., 43, 185-190 (1992) · Zbl 0763.68048
[3] Birget, J. C., Partial orders on words, minimal elements of regular languages, and state complexity, Theoret. Comput. Sci., 119, 267-291 (1993) · Zbl 0786.68071
[4] J.C. Birget, ERRATUM: partial orders on words, minimal elements of regular languages, and state complexity, 2002. Available at: \( \sim;\); J.C. Birget, ERRATUM: partial orders on words, minimal elements of regular languages, and state complexity, 2002. Available at: \( \sim;\)
[5] Câmpeanu, C.; Culik II, K.; Salomaa, K.; Yu, S., State complexity of basic operations on finite languages, (Boldt, O.; Jürgensen, H., Proc. Fourth Internat. Workshop on Implementing Automata (WIA’99), Lecture Notes in Computer Science, Vol. 2214 (2001), Springer: Springer Heidelberg), 60-70 · Zbl 1050.68091
[6] Câmpeanu, C.; Salomaa, K.; Yu, S., Tight lower bound for the state complexity of shuffle of regular languages, J. Automat. Lang. Comb., 7, 303-310 (2002) · Zbl 1033.68057
[7] Domaratzki, M., State complexity and proportional removals, J. Automat. Lang. Comb., 7, 455-468 (2002) · Zbl 1095.68605
[8] K. Ellul, Descriptional complexity measures of regular languages, Master’s thesis, University of Waterloo, 2002.; K. Ellul, Descriptional complexity measures of regular languages, Master’s thesis, University of Waterloo, 2002.
[9] Glaister, I.; Shallit, J., A lower bound technique for the size of nondeterministic finite automata, Inform. Process. Lett., 59, 75-77 (1996) · Zbl 0900.68313
[10] M. Holzer, M. Kutrib, Nondeterministic descriptional complexity of regular languages, Internat. J. Found. Comput. Sci. (to appear). Preprint: IFIG Research Report 0205, University of Giessen, 2002. Available at:; M. Holzer, M. Kutrib, Nondeterministic descriptional complexity of regular languages, Internat. J. Found. Comput. Sci. (to appear). Preprint: IFIG Research Report 0205, University of Giessen, 2002. Available at: · Zbl 1101.68657
[11] M. Holzer, M. Kutrib, Unary language operations and their nondeterministic state complexity, in: M. Ito, M. Toyama (Eds.) Developments in Language Theory (DLT 2002), Lecture Notes in Computer Science, Vol. 2450, Springer, Heidelberg, 2003, pp. 162-172.; M. Holzer, M. Kutrib, Unary language operations and their nondeterministic state complexity, in: M. Ito, M. Toyama (Eds.) Developments in Language Theory (DLT 2002), Lecture Notes in Computer Science, Vol. 2450, Springer, Heidelberg, 2003, pp. 162-172. · Zbl 1015.68118
[12] M. Holzer, M. Kutrib, State complexity of basic operations on nondeterministic finite automata, in: J.M. Champarnaud, D. Maurel (Eds.), Implementation and Application of Automata (CIAA 2002), Lecture Notes in Computer Science, Vol. 2608, Springer, Heidelberg, 2003, pp. 148-157.; M. Holzer, M. Kutrib, State complexity of basic operations on nondeterministic finite automata, in: J.M. Champarnaud, D. Maurel (Eds.), Implementation and Application of Automata (CIAA 2002), Lecture Notes in Computer Science, Vol. 2608, Springer, Heidelberg, 2003, pp. 148-157. · Zbl 1033.68063
[13] Holzer, M.; Salomaa, K.; Yu, S., On the state complexity of \(k\)-entry deterministic finite automata, J. Automat. Lang. Comb., 6, 453-466 (2001) · Zbl 1050.68093
[14] Hromkovič, J., Communication Complexity and Parallel Computing (1997), Springer: Springer Berlin, Heidelberg · Zbl 0873.68098
[15] Hromkovič, J., Descriptional complexity of finite automataconcepts and open problems, J. Automat. Lang. Comb., 7, 519-531 (2002) · Zbl 1094.68576
[16] Hromkovič, J.; Seibert, S.; Karhumäki, J.; Klauck, H.; Schnitger, G., Communication complexity method for measuring nondeterminism in finite automata, Inform. and Comput., 172, 202-217 (2002) · Zbl 1009.68067
[17] Jirásková, G., Note on minimal automata and uniform communication protocols, (Martin-Vide, C.; Mitrana, V., Grammars and Automata for String Processing: From Mathematics and Computer Science to Biology, and Back (2003), Taylor and Francis: Taylor and Francis London), 163-170 · Zbl 1103.68583
[18] Leiss, E., Succinct representation of regular languages by boolean automata, Theoret. Comput. Sci., 13, 323-330 (1981) · Zbl 0458.68017
[19] Lupanov, O. B., A comparison of two types of finite automata, Problemy Kibernetiki, 9, 321-326 (1963), (in Russian)
[20] Meyer, A. R.; Fischer, M. J., Economy of description by automata, grammars and formal systems, (Proc. 12th Annual Symposium on Switching and Automata Theory (1971)), 188-191
[21] 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
[22] G. Pighizzini, Unary language concatenation and its state complexity, in: S. Yu, A. Pun (Eds.), Implementation and Application of Automata: Fifth Internat. Conference, CIAA 2000, Lecture Notes in Computer Science, Vol. 2088, Springer, Heidelberg, 2001, pp. 252-262.; G. Pighizzini, Unary language concatenation and its state complexity, in: S. Yu, A. Pun (Eds.), Implementation and Application of Automata: Fifth Internat. Conference, CIAA 2000, Lecture Notes in Computer Science, Vol. 2088, Springer, Heidelberg, 2001, pp. 252-262. · Zbl 0989.68081
[23] Pighizzini, G.; Shallit, J., Unary language operations, state complexity and Jacobsthal’s function, Internat. J. Found. Comput. Sci., 13, 145-159 (2002) · Zbl 1066.68072
[24] Rabin, M.; Scott, D., Finite automata and their decision problems, IBM Res. Develop., 3, 114-129 (1959) · Zbl 0158.25404
[25] Sakoda, W. J.; Sipser, M., Nondeterminism and the size of two-way finite automata, (Proc. 10th Ann. ACM Symp. on Theory of Computing (1978)), 275-286 · Zbl 1282.68160
[26] Sipser, M., Introduction to the Theory of Computation (1997), PWS Publishing Company: PWS Publishing Company Boston · Zbl 1169.68300
[27] S. Yu, Regular languages, in: G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Vol. 1, Springer, Berlin, New York, pp. 41-110 (Chapter 2).; S. Yu, Regular languages, in: G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Vol. 1, Springer, Berlin, New York, pp. 41-110 (Chapter 2).
[28] Yu, S.; Zhuang, Q.; Salomaa, K., The state complexity of some basic operations on regular languages, Theoret. Comput. Sci., 125, 315-328 (1994) · Zbl 0795.68112
[29] Yu, S., State complexity of regular languages, J. Automat. Lang. Comb., 6, 221-234 (2001) · Zbl 0978.68087
[30] Yu, S., A renaissance of automata theory, Bull. Eur. Assoc. Theoret. Comput. Sci. EATCS, 72, 270-272 (2000)
[31] Yu, S., State complexity of finite and infinite regular languages, Bull. Eur. Assoc. Theoret. Comput. Sci. EATCS, 76, 270-272 (2000)
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.