×

State complexity of combined operations. (English) Zbl 1124.68056

Summary: We study the state complexity of combined operations. Two particular combined operations are studied: star of union and star of intersection. It is shown that the state complexity of a combined operation is not necessarily similar to the combination of the individual state complexities of the participating operations.

MSC:

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

References:

[1] Birget, J.-C., Partial orders on words, minimal elements of regular languages, and state complexity, Theoretical Computer Science, 119, 267-291 (1993) · Zbl 0786.68071
[2] Campeanu, C.; Culik, K.; Salomaa, K.; Yu, S., State complexity of basic operations on finite languages, (Proceedings of the Fourth International Workshop on Implementing Automata VIII 1-11. Proceedings of the Fourth International Workshop on Implementing Automata VIII 1-11, LNCS, vol. 2214 (1999)), 60-70 · Zbl 1050.68091
[3] Campeanu, C.; Salomaa, K.; Yu, S., Tight lower bound for the state complexity of shuffle of regular languages, Journal of Automata, Languages and Combinatorics, 7, 3, 303-310 (2002) · Zbl 1033.68057
[4] Campeanu, C.; Salomaa, K.; Yu, S., Chapter 5: state complexity of regular languages: finite versus infinite, (Calude, C.; Paun, G., Finite vs Infinite — Contributions to an Eternal Dilemma (2000), Springer), 53-73
[5] Domaratzki, M., State complexity and proportional removals, Journal of Automata, Languages and Combinatorics, 7, 455-468 (2002) · Zbl 1095.68605
[6] Holzer, M.; Kutrib, M., State complexity of basic operations on nondeterministic finite automata, (Proceedings of International Conference on Implementation and Application of Automata 2002, CIAA 2002. Proceedings of International Conference on Implementation and Application of Automata 2002, CIAA 2002, LNCS, vol. 2608 (2002), Springer), 148-157 · Zbl 1033.68063
[7] Holzer, M.; Kutrib, M., Unary language operations and their nondeterministic state complexity, (Developments in Language Theory, DLT 2002. Developments in Language Theory, DLT 2002, LNCS, vol. 2450 (2002), Springer), 162-172 · Zbl 1015.68118
[8] Holzer, M.; Salomaa, K.; Yu, S., On the state complexity of k-entry deterministic finite automata, Journal of Automata, Languages and Combinatorics, 6, 4, 453-466 (2001) · Zbl 1050.68093
[9] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison Wesley: Addison Wesley Reading, Mass · Zbl 0196.01701
[10] Iwama, K.; Kambayashi, Y.; Takaki, K., Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs, Theoretical Computer Science, 237, 485-494 (2000) · Zbl 0939.68068
[11] G. Jirásková, State complexity of some operations on regular languages, in: Proceedings of 5th Workshop on Descriptional Complexity of Formal Systems, 2003, pp. 114-125; G. Jirásková, State complexity of some operations on regular languages, in: Proceedings of 5th Workshop on Descriptional Complexity of Formal Systems, 2003, pp. 114-125
[12] Jirásková, G., State complexity of some operations on binary regular languages, Theoretical Computer Science, 330, 287-298 (2005) · Zbl 1078.68088
[13] Jirásek, J.; Jirásková, G.; Szabari, A., State complexity of concatenation and complementation of regular languages, International Journal of Foundations of Computer Science, 16, 511-529 (2005) · Zbl 1097.68062
[14] G. Jirásková, A. Okhotin, State complexity of cyclic shift, in: Proceedings of DCFS 2005, Como, Italy, June 30-July 2, 2005, pp. 182-193; G. Jirásková, A. Okhotin, State complexity of cyclic shift, in: Proceedings of DCFS 2005, Como, Italy, June 30-July 2, 2005, pp. 182-193
[15] Nicaud, C., Average State Complexity of Operations on Unary Automata, (MFCS’99. MFCS’99, LNCS, vol. 1672 (1999)), 231-240 · Zbl 0955.68068
[16] Pighizzini, G.; Shallit, J., Unary language operations, state complexity and Jacobsthal’s function, International Journal of Foundations of Computer Science, 13, 1, 145-159 (2002) · Zbl 1066.68072
[17] Salomaa, A., Theory of Automata (1969), Pergamon Press: Pergamon Press Oxford · Zbl 0193.32901
[18] Salomaa, A.; Wood, D.; Yu, S., On the state complexity of reversals of regular languages, Theoretical Computer Science, 320, 293-313 (2004)
[19] Salomaa, K.; Yu, S., NFA to DFA transformation for finite languages over arbitrary alphabets, Journal of Automata, Languages and Combinatorics, 2, 3, 177-186 (1997) · Zbl 0897.68060
[20] Yu, S., State complexity of regular languages, Journal of Automata, Languages and Combinatorics, 6, 2, 221-234 (2001) · Zbl 0978.68087
[21] Yu, S.; Zhuang, Q.; Salomaa, K., The state complexities of some basic operations on regular languages, Theoretical Computer Science, 125, 315-328 (1994) · Zbl 0795.68112
[22] Yu, S., Regular languages, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, Vol. 1 (1997), Springer-Verlag), 41-110
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.