State complexity of four combined operations composed of union, intersection, star and reversal
Authors: 
Yuan Gao, Sheng YuAuthors Info & Claims
Pages 158 - 171
Abstract
In this paper, we study the state complexities of union and intersection combined with star and reversal, respectively. We obtain the exact bounds for these combined operations on regular languages and show that, as usually, they are different from the mathematical compositions of the state complexities of their individual participating operations.
References
[1]
Cui, B., Gao, Y., Kari, L., Yu, S.: State complexity of catenation combined with star and reversal. In: Proceedings of Descriptional Complexity of Formal Systems 12th Workshop, Saskatoon, pp. 74-85 (2010)
[2]
Cui, B., Gao, Y., Kari, L., Yu, S.: State complexity of catenation combined with union and intersection. In: Domaratzki, M., Salomaa, K. (eds.) CIAA 2010. LNCS, vol. 6482, pp. 95-104. Springer, Heidelberg (2011)
[3]
Câmpeanu, C., Culik, K., Salomaa, K., Yu, S.: State complexity of basic operations on finite languages. In: Boldt, O., Jürgensen, H. (eds.) WIA 1999. LNCS, vol. 2214, pp. 60-70. Springer, Heidelberg (2001)
[4]
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)
[5]
Daley, M., Domaratzki, M., Salomaa, K.: State complexity of orthogonal catenation. In: Proceedings of Descriptional Complexity of Formal Systems 10th Workshop, Charlottetown, pp. 134-144 (2008)
[6]
Domaratzki, M.: State complexity and proportional removals. Journal of Automata, Languages and Combinatorics 7, 455-468 (2002)
[7]
Domaratzki, M., Okhotin, A.: State complexity of power. Theoretical Computer Science 410(24-25), 2377-2392 (2009)
[8]
ésik, Z., Gao, Y., Liu, G., Yu, S.: Estimation of State Complexity of Combined Operations. Theoretical Computer Science 410(35), 3272-3280 (2008)
[9]
Gao, Y., Salomaa, K., Yu, S.: The state complexity of two combined operations: star of catenation and star of Reversal. Fundamenta Informaticae 83(1-2), 75-89 (2008)
[10]
Gao, Y., Yu, S.: State complexity approximation. Electronic Proceedings in Theoretical Computer Science 3, 121-130 (2009)
[11]
Holzer, M., Kutrib, M.: State complexity of basic operations on nondeterministic finite automata. In: Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2002. LNCS, vol. 2608, pp. 148-157. Springer, Heidelberg (2003)
[12]
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison Wesley, Reading (2001)
[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)
[14]
Jirásková, G.: State complexity of some operations on binary regular languages. Theoretical Computer Science 330, 287-298 (2005)
[15]
Jirásková, G., Okhotin, A.: State complexity of cyclic shift. In: Proceedings of Descriptional Complexity of Formal Systems 7th Workshop, Como, pp. 182-193 (2005)
[16]
Jirásková, 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 (2007)
[17]
Liu, G., Martin-Vide, C., Salomaa, A., Yu, S.: State complexity of basic language operations combined with reversal. Information and Computation 206, 1178-1186 (2008)
[18]
Maslov, A.N.: Estimates of the number of states of finite automata. Soviet Mathematics Doklady 11, 1373-1375 (1970)
[19]
Pighizzini, G., Shallit, J.O.: Unary language operations, state complexity and Jacobsthal's function. International Journal of Foundations of Computer Science 13, 145-159 (2002)
[20]
Rabin, M., Scott, D.: Finite automata and their decision problems. IBM Journal of Research and Development 3(2), 114-125 (1959)
[21]
Salomaa, A., Salomaa, K., Yu, S.: State complexity of combined operations. Theoretical Computer Science 383, 140-152 (2007)
[22]
Salomaa, A., Wood, D., Yu, S.: On the state complexity of reversals of regular languages. Theoretical Computer Science 320, 293-313 (2004)
[23]
Yu, S.: State complexity of regular languages. Journal of Automata, Languages and Combinatorics 6(2), 221-234 (2001)
[24]
Yu, S., Zhuang, Q., Salomaa, K.: The state complexity of some basic operations on regular languages. Theoretical Computer Science 125, 315-328 (1994)
[25]
Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1, pp. 41-110. Springer, Heidelberg (1997)
[26]
Yu, S.: On the state complexity of combined operations. In: Ibarra, O.H., Yen, H.-C. (eds.) CIAA 2006. LNCS, vol. 4094, pp. 11-22. Springer, Heidelberg (2006)
- State complexity of four combined operations composed of union, intersection, star and reversal
Recommendations
State complexity of catenation combined with union and intersection
CIAA'10: Proceedings of the 15th international conference on Implementation and application of automataIn this paper, we study the state complexities of two particular combinations of operations: catenation combined with union and catenation combined with intersection. We show that the state complexity of the former combined operation is considerably ...
State Complexity of Combined Operations with Union, Intersection, Star and Reversal
Words, Graphs, Automata, and Languages; Special Issue Honoring the 60th Birthday of Professor Tero HarjuIn this paper, we study the state complexities of four combined operations: L*1 ∪ L2, L*1 ∩ L2, LR1 ∪ L2, and LR1 ∩ L2. The tight bounds for all these combined operations on regular languages are obtained and proved. We show that, as usual, they are ...
State complexity of combined operations
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 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 25 July 2011
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 21 Nov 2024