Special Issue Implementation and Application of Automata (CIAA 2010)No Access
STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-UNION AND CATENATION-INTERSECTION
https://doi.org/10.1142/S0129054111009045Cited by:11 (Source: Crossref)
Abstract
In 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 less than the mathematical composition of the state complexities of catenation and union, while the state complexity of the latter one is equal to the mathematical composition of the state complexities of catenation and intersection.
This work is supported by Natural Science and Engineering Council of Canada Discovery Grant R2824A01, Canada Research Chair Award, and Natural Science and Engineering Council of Canada Discovery Grant 41630.
References
- Mathematical Systems Theory 26(3), 237 (1993), DOI: 10.1007/BF01371727. Crossref, Google Scholar
C. Campeanu , State complexity of basic operations on finite language, Proceedings of the Fourth International Workshop on Implementing AutomataVIII,LNCS 2214 (1999) pp. 60–70. Google Scholar- Journal of Automata, Languages and Combinatorics 7, 455 (2002). Google Scholar
- Theoretical Computer Science 410(24-25), 2377 (2009), DOI: 10.1016/j.tcs.2009.02.025. Crossref, Web of Science, Google Scholar
- Theoretical Computer Science 410(35), 3272 (2009). Crossref, Web of Science, Google Scholar
- Fundam. Inform. 83(1-2), 75 (2008). Web of Science, Google Scholar
Y. Gao and S. Yu , State complexity approximation, Proceedings of Descriptional Complexity of Formal Systems (2009) pp. 163–174. Google Scholar- Theoretical Computer Science 410(27-29), 2537 (2009), DOI: 10.1016/j.tcs.2008.12.054. Crossref, Web of Science, Google Scholar
M. Holzer and M. Kutrib , State complexity of basic operations on nondeterministic finite automata, Proceedings of International Conference on Implementation and Application of Automata 2002,LNCS 2608 (2002) pp. 148–157. Google Scholar-
J. E. Hopcroft and J. D. Ullman , Introduction to Automata Theory, Languages, and Computation ( Addison Wesley , 1979 ) . Google Scholar - International Journal of Foundations of Computer Science 16, 511 (2005). Link, Web of Science, Google Scholar
- Theoretical Computer Science 330, 287 (2005). Crossref, Web of Science, Google Scholar
- 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 . Google Scholar
- Information and Computation 206, 1178 (2008), DOI: 10.1016/j.ic.2008.03.018. Crossref, Web of Science, Google Scholar
- Soviet Mathematics Doklady 11, 1373 (1970). Google Scholar
- International Journal of Foundations of Computer Science 13, 145 (2002), DOI: 10.1142/S012905410200100X. Link, Web of Science, Google Scholar
- Information Processing Letters 98, 231 (2006), DOI: 10.1016/j.ipl.2005.06.011. Crossref, Web of Science, Google Scholar
- Theoretical Computer Science 320, 293 (2004), DOI: 10.1016/j.tcs.2004.02.032. Web of Science, Google Scholar
- Theoretical Computer Science 383, 140 (2007), DOI: 10.1016/j.tcs.2007.04.015. Crossref, Web of Science, Google Scholar
- Theoretical Computer Science 125, 315 (1994), DOI: 10.1016/0304-3975(92)00011-F. Crossref, Web of Science, Google Scholar
- , Handbook of Formal Languages 1, eds.
G. Rozenberg and A. Salomaa (Springer-Verlag, 1997) pp. 41–110. Crossref, Google Scholar - Journal of Automata, Languages and Combinatorics 6(2), 221 (2001). Web of Science, Google Scholar
| Remember to check out the Most Cited Articles! |
|---|
|
Check out these Handbooks in Computer Science |
