State Complexity of Combined Operations with Union, Intersection, Star and Reversal

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

Abstrakty

EN

In this paper, we study the state complexities of four combined operations: [formula]. The tight bounds for all these combined operations on regular languages are obtained and proved. We show that, as usual, they are different from the mathematical compositions of the state complexities of their individual participating operations.

Słowa kluczowe

EN

state complexity; combined operations; regular language; finite automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 116, nr 1-4
• Strony: 79--92
• Opis fizyczny: Bibliogr. 27 poz., rys.

Twórcy

autor

Gao Y.

autor

Yu S

• Department of Computer Science, The University of Western Ontario London, Ontario, Canada N6A 5B7,

Bibliografia

• [1] B. Cui, Y. Gao, L. Kari, S. Yu: State complexity of combined operationswith two basic operations, subtmitted to: Theoretical Computer Science Science (TCS), 2011
• [2] B. Cui, Y. Gao, L. Kari, S. Yu: State complexity of catenation combined with star and reversal, in: Proceedings of Descriptional Complexity of Formal Systems 12thWorkshop, Saskatoon, 2010, 74-85
• [3] B. Cui, Y. Gao, L. Kari, S. Yu: State complexity of catenation combined with union and intersection, in: Proceedings of 15th International Conference on Implementation and Application of Automata, Springer LNCS 6482, 2010, 95-104
• [4] C. Campeanu, K. Culik, K. Salomaa, S. Yu: State complexity of basic operations on finite language, in: Proceedings of 4th InternationalWorkshop on Implementing Automata, VIII 1-11, LNCS 2214, 1999, 60-70
• [5] 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 (3) (2002) 303-310
• [6] M. Daley, M. Domaratzki, K. Salomaa: State complexity of orthogonal catenation, in: Proceedings of Descriptional Complexity of Formal Systems 10thWorkshop, Charlottetown, 2008, 134-144
• [7] M. Domaratzki: State complexity and proportional removals, Journal of Automata, Languages and Combinatorics 7 (2002) 455-468
• [8] M. Domaratzki, A. Okhotin: State complexity of power, Theoretical Computer Science 410 (24-25) (2009) 2377-2392
• [9] Z.Ésik, Y. Gao, G. Liu, S. Yu: Estimation of State Complexity of Combined Operations, Theoretical Computer Science 410 (35) (2008) 3272-3280.
• [10] 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
• [11] Y. Gao, S. Yu: State complexity approximation, Electronic Proceedings in Theoretical Computer Science 3 (2009) 121-130
• [12] M. Holzer,M. Kutrib: State complexity of basic operations on nondeterministic finite automata, in: Proceedings of 7th International Conference on Implementation and Application of Automata, LNCS 2608, 2002, 148-157
• [13] J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation (2nd Edition), AddisonWesley, 2001
• [14] J. Jirásek, G. Jirásková, A. Szabari: State complexity of concatenation and complementation of regular languages, International Journal of Foundations of Computer Science 16 (2005) 511-529
• [15] G. Jirásková: State complexity of some operations on binary regular languages, Theoretical Computer Science 330 (2005) 287-298
• [16] G. Jirásková, A. Okhotin: State complexity of cyclic shift, in: Proceedings of Descriptional Complexity of Formal Systems 7th Workshop, Como, 2005, 182-193
• [17] G. Jirásková, A. Okhotin: On the state complexity of star of union and star of intersection, Turku Center for Computer Science TUCS Technical Report No. 825, 2007
• [18] G. Liu, C. Martin-Vide, A. Salomaa, S. Yu: State complexity of basic language operations combined with reversal, Information and Computation 206 (2008) 1178-1186
• [19] A. N. Maslov: Estimates of the number of states of finite automata, Soviet Mathematics Doklady 11 (1970) 1373-1375
• [20] G. Pighizzini, J. O. Shallit: Unary language operations, state complexity and Jacobsthal's function, International Journal of Foundations of Computer Science 13 (2002) 145-159
• [21] M. Rabin, D. Scott: Finite automata and their decision problems, IBMJournal of Research and Development, 3 (2) (1959) 114-125
• [22] A. Salomaa, K. Salomaa, S. Yu: State complexity of combined operations, Theoretical Computer Science 383 (2007) 140-152
• [23] A. Salomaa, D.Wood, S. Yu: On the state complexity of reversals of regular languages, Theoretical Computer Science 320 (2004) 293-313
• [24] S. Yu: State complexity of regular languages, Journal of Automata, Languages and Combinatorics 6 (2) (2001) 221-234
• [25] S. Yu, Q. Zhuang, K. Salomaa: The state complexity of some basic operations on regular languages, Theoretical Computer Science 125 (1994) 315-328
• [26] S. Yu: Regular languages, in: G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Vol. 1, Springer, 1997, 41-110
• [27] S. Yu: On the state complexity of combined operations, in: Proceedings of 11th International Conference on Implementation and Application of Automata, Springer LNCS 4094, 2006, 11-22