On the State Complexity of Star of Union and Star of Intersection

• Autorzy: Jiraskova, G. , Okhotin, A.
• Języki publikacji: EN

Abstrakty

EN

The state complexity of the star of union of anm-state DFA language and an n-state DFA language is proved to be 2^m+n-1 - 2^m-1 - 2^n-1 +1 for every alphabet of at least two letters. The state complexity of the star of intersection is established as [...} for every alphabet of six or more letters. This improves the recent results of A. Salomaa, K. Salomaa and Yu ("State complexity of combined operations", Theoret. Comput. Sci., 383 (2007) 140–152).

Słowa kluczowe

EN

descriptional complexity; finite automata; state complexity; combined operations

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 109, nr 2
• Strony: 161-178
• Opis fizyczny: Bibliogr. 9 poz., wykr.

Twórcy

autor

Jiraskova, G.

autor

Okhotin, A.

• Department of Mathematics, University of Turku, Turku FIN–20014, Finland,

Bibliografia

• [1] C. Campeanu, K. Salomaa, S. Yu, "Tight lower bound for the state complexity of shuffle of regular languages", Journal of Automata, Languages and Combinatorics, 7 (2002), 303-310.
• [2] M. Domaratzki, A. Okhotin, "State complexity of power", Theoretical Computer Science, 410:24-25 (2009), 2377-2392.
• [3] Y. Gao, K. Salomaa, S. Yu, "The state complexity of two combined operations: star of catenation and star of reversal", Fundamenta Informaticae, 83:1-2 (2008), 75-89.
• [4] G. Jirásková, "State complexity of some operations on binary regular languages", Theoretical Computer Science, 330 (2005), 287-298.
• [5] G. Jirásková, A. Okhotin, "State complexity of cyclic shift", RAIRO Informatique Théorique et Applications, 42:2 (2008), 335-360.
• [6] G. Liu, C. Martın-Vide, A. Salomaa, S. Yu, "State complexity of basic operations combined with reversal", Information and Computation, 206:9-10 (2008), 1178-1186.
• [7] A. N.Maslov, "Estimates of the number of states of finite automata", SovietMathematics Doklady, 11 (1970), 1373-1375.
• [8] A. Salomaa, K. Salomaa, S. Yu, "State complexity of combined operations", Theoretical Computer Science, 383:2-3 (2007), 140-152.
• [9] S. Yu, Q. Zhuang, K. Salomaa, "The state complexity of some basic operations on regular languages", Theoretical Computer Science, 125 (1994), 315-328.