Special Issue Implementation and Application of Automata (CIAA 2010)No Access

STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-UNION AND CATENATION-INTERSECTION

BO CUI

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

Search for more papers by this author

YUAN GAO

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

Corresponding author.

Search for more papers by this author

LILA KARI

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

Search for more papers by this author

, and

SHENG YU

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

Search for more papers by this author

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.

Keywords:

References

J. Birget, Mathematical Systems Theory 26(3), 237 (1993), DOI: 10.1007/BF01371727. Crossref, Google Scholar
C. Campeanuet al., 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
M. Domaratzki, Journal of Automata, Languages and Combinatorics 7, 455 (2002). Google Scholar
M. Domaratzki and A. Okhotin, Theoretical Computer Science 410(24-25), 2377 (2009), DOI: 10.1016/j.tcs.2009.02.025. Crossref, Web of Science, Google Scholar
Z. Ésiket al., Theoretical Computer Science 410(35), 3272 (2009). Crossref, Web of Science, Google Scholar
Y. Gao, K. Salomaa and S. Yu, 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
Y. Han and K. Salomaa, 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
J. Jirásek, G. Jirásková and A. Szabari, International Journal of Foundations of Computer Science 16, 511 (2005). Link, Web of Science, Google Scholar
G. Jirásková, 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
G. Liuet al., Information and Computation 206, 1178 (2008), DOI: 10.1016/j.ic.2008.03.018. Crossref, Web of Science, Google Scholar
A. N. Maslov, Soviet Mathematics Doklady 11, 1373 (1970). Google Scholar
G. Pighizzini and J. Shallit, International Journal of Foundations of Computer Science 13, 145 (2002), DOI: 10.1142/S012905410200100X. Link, Web of Science, Google Scholar
N. Rampersad, Information Processing Letters 98, 231 (2006), DOI: 10.1016/j.ipl.2005.06.011. Crossref, Web of Science, Google Scholar
A. Salomaa, D. Wood and S. Yu, Theoretical Computer Science 320, 293 (2004), DOI: 10.1016/j.tcs.2004.02.032. Web of Science, Google Scholar
A. Salomaa, K. Salomaa and S. Yu, Theoretical Computer Science 383, 140 (2007), DOI: 10.1016/j.tcs.2007.04.015. Crossref, Web of Science, Google Scholar
S. Yu, Q. Zhuang and K. Salomaa, Theoretical Computer Science 125, 315 (1994), DOI: 10.1016/0304-3975(92)00011-F. Crossref, Web of Science, Google Scholar
S. Yu, Handbook of Formal Languages 1, eds. G. Rozenberg and A. Salomaa (Springer-Verlag, 1997) pp. 41–110. Crossref, Google Scholar
S. Yu, Journal of Automata, Languages and Combinatorics 6(2), 221 (2001). Web of Science, Google Scholar