The State Complexity of Two Combined Operations: Star of Catenation and Star of Reversal

• Autorzy: Gao Y. , Salomaa K. , Yu S
• Języki publikacji: EN

Abstrakty

EN

The state complexity of two combined operations, star of catenation and star of reversal, on regular languages is considered in this paper. Tight bounds are obtained for both combined operations. The results clearly show that the state complexity of a combined operation can be very different from the composition of the state complexities of its participating individual operations. A new approach for research in automata and formal language theory is also explained.

Słowa kluczowe

EN

state complexity; deterministic finite automaton

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 83, nr 1-2
• Strony: 75--89
• Opis fizyczny: . bibliogr. 23 poz.

Twórcy

autor

Gao Y.

autor

Salomaa K.

autor

Yu S

• School of Computing, Queenćs University, Kingston, Ontario, Canada K7L3N6,

Bibliografia

• [1] Campeanu, C, Culik II, K., Salomaa, K., Yu, S.: State complexity of basic operations on finite languages, Proceedings of the Fourth International Workshop on Implementing Automata, Led. Notes Comput. Sci. 2214, Springer-Verlag, 1999, 60-70.
• [2] 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, 2002, 303-310
• [3] Campeanu, C, Salomaa, K., Yu, S.: State complexity of regular languages: Finite versus infinite (Chapter 5), in: Finite vs Infinite - Contributions to an Eternal Dilemma, (C. Calude and G. Paun, Eds.) Springer, 2000, 53-73.
• [4] Domaratzki, M.: State complexity and proportional removals, Journal of Automata, Languages and Combinatorics 7, 2002,455-468.
• [5] Han, Y.-S., Salomaa, K.: State complexity of basic operations on suffix-free regular languages, in: Proceedings ofMFCS'07, Lect. Notes Comput. Sci. 4708, Springer-Verlag, 2007, 501-512.
• [6] Holzer, M., Kutrib, M.: Nondeterministic descriptional complexity of regular languages, International Journal of Foundations of Computer Science 14, 2003, 1087-1102.
• [7] Holzer, M., Salomaa, K., Yu, S.: On the state complexity of k-entry deterministic finite automata, Journal of Automata, Languages and Combinatorics 6, 2001, 453-466.
• [8] Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, Reading, Mass., 1979.
• [9] Jiraskova, G.: State complexity of some operations on regular languages, Theoretical Computer Science 330, 2005, 287-298.
• [10] Jirasek, J., Jiraskova, G., Szabari, A.: State complexity of concatenation and complementation of regular languages, International Journal of Foundations of Computer Science 16, 2005, 511-529.
• [11] Jiraskova, G., Okhotin, A.: State complexity of cyclic shift, in: Proceedings of DCFS 2005, (Como, Italy, June 30 - July 2, 2005), 182-193.
• [12] Jiraskova, G., Okhotin, A., On the state complexity of star of union and star of intersection, Turku Center for Computer Science TUCS Technical Report No. 825, August 2007.
• [13] Leiss, E.: Succinct representation of regular languages by boolean automata II, Theoretical Computer Science 13, 1981,323-330.
• [14] Nicaud, C: Average state complexity of operations on unary automata, in: Proceedings ofMFCS'99, Lect. Notes Comput. Sci. 1672, Springer-Verlag, 1999, 231-240.
• [15] Pighizzini, G., Shallit, J.: Unary language operations, state complexity and Jacobsthal's function, International Journal of Foundations of Computer Science 13, 2002, 145-159.
• [16] Salomaa, A.: Theory of Automata, Pergamon Press, Oxford, 1969.
• [17] Salomaa, A., Salomaa, K., Yu, S.: State complexity of combined operations, Theoretical Computer Science 383, 2007,140-152.
• [18] Salomaa, A., Wood, D., Yu, S.: On the state complexity of reversals of regular languages, Theoretical Computer Science 320, 2004,293-313.
• [19] Salomaa, K., Yu, S.: NFA to DFA transformation for finite languages over arbitrary alphabets, Journal of Automata, Languages and Combinatorics 2, 1997, 177-186.
• [20] Yu,S.: Regular languages, in: Handbook ofFormal Languages,Vo\. 1, (G.Rozenberg and A. Salomaa, Eds.), Springer-Verlag, 1997,41-110.
• [21] Yu, S.: State complexity of regular languages, Journal of Automata, Languages and Combinatorics 6, 2001, 221-234.
• [22] Yu, S.: Grail+: A symbolic computation environment for finite-state machines, regular expressions and finite languages, http: //www. csd.uwo. ca/Research/grail, 2002.
• [23] Yu, S., Zhuang , Q., Salomaa, K.: The state-complexities of some basic operations on regular languages, Theoretical Computer Science 125, 1994, 315-328.