Special Issue: Implementation and Application of Automata: Invited PapersNo Access

ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION

KAI SALOMAA

School of Computing, Queen's University, Kingston, Ontario, Canada K7L 3N6, Canada

Search for more papers by this author

and

SHENG YU

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

Search for more papers by this author

https://doi.org/10.1142/S0129054107004917Cited by:23 (Source: Crossref)

Abstract

We consider the state complexity of several combined operations. Those results show that the state complexity of a combined operation is in general very different from the composition of the state complexities of the participating individual operations. We also consider general estimation methods for the state complexity of combined operations. In particular, estimation through nondeterministic state complexity is studied. It is shown that the method is very promising for a large class of combined operations.

This paper is based on the invited talk at CIAA 2006 given by Sheng Yu. This work is partially supported by the Natural Sciences and Engineering Council of Canada grants OGP0041630 and OGP0147224.

Keywords:

References

J.-C. Birget, Theoretical Computer Science 119, 267 (1993), DOI: 10.1016/0304-3975(93)90160-U. Crossref, Web of Science, Google Scholar
G. V. Bochmann, Submodule Construction and Supervisory Control: A Generalization, 6th International Conference on Implementation and Application of Automata (CIAA 2001), LNCS 2494 (Springer) pp. 27–39. Google Scholar
C. Câmpeanuet al., State Complexity of Basic Operations on Finite Languages, Proceedings of the Fourth International Workshop on Implementing Automata VIII 1–11, LNCS 2214 pp. 60–70. Google Scholar
C. Câmpeanu, K. Salomaa and S. Yu, Journal of Automata, Languages and Combinatorics 7(3), 303 (2002). Google Scholar
C. Câmpeanu, K. Salomaa and S. Yu, Finite vs Infinite – Contributions to an Eternal Dilemma, eds. C. Calude and G. Paun (Springer, 2000) pp. 53–73. Google Scholar
M. Domaratzki, Journal of Automata, Languages and Combinatorics 7, 455 (2002). Google Scholar
K. Ellulet al., J. Automata, Languages and Combinatorics 9, 233 (2004). Web of Science, Google Scholar
Y. Gao, K. Salomaa and S. Yu, State complexity of catenation and reversal combined with star, Proc. Descriptional Complexity of Formal Systems DCFS'06, eds. H. Leung and G. Pighizzini (2006) pp. 153–164. Google Scholar
D. Harel and M. Politi , Modeling Reactive Systems with Statecharts ( McGraw-Hill , 1998 ) . Google Scholar
M. Holzer and M. Kutrib, Internat. J. Foundations Comput. Sci. 14, 1087 (2003), DOI: 10.1142/S0129054103002199. Link, Google Scholar
M. Holzer and M. Kutrib, Unary language operations and their nondeterministic state complexity, Developments in Language Theory (DLT 2002), LNCS 2450 (Springer) pp. 162–172. Google Scholar
J. E. Hopcroft and J. D. Ullman , Introduction to Automata Theory, Languages, and Computation ( Addison Wesley , Reading, Mass , 1979 ) . Google Scholar
K. Iwama, Y. Kambayashi and K. Takaki, Theoretical Computer Science 237, 485 (2000), DOI: 10.1016/S0304-3975(00)00029-3. Crossref, Web of Science, Google Scholar
G. Jirásková, Theoretical Computer Science 330, 287 (2005). Crossref, Web of Science, 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
L. Karttunen, Applications of Finite-State Transducers in Natural Language Processing, 5th International Conference on Implementation and Application of Automata (CIAA 2000), LNCS 2088 (Springer) pp. 34–46. Google Scholar
E. Leiss, Theoretical Computer Science 13, 323 (1981), DOI: 10.1016/S0304-3975(81)80005-9. Crossref, Web of Science, Google Scholar
G. Liu, C. Martin-Vide, A. Salomaa and S. Yu, "State complexity of basic operations combined with reversal", submitted for publication . Google Scholar
C. Nicaud, Average State Complexity of Operations on Automata, MFCS'99, LNCS 1672 (Springer) pp. 231–240. 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 , Theory of Automata ( Pergamon Press , Oxford , 1969 ) . Google Scholar
A. Salomaa, K. Salomaa, S. Yu, "State Complexity of Combined Operations", Theoretical Computer Science, to appear . 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
K. Salomaa and S. Yu, Journal of Automata, Languages and Combinatorics 2(3), 177 (1997). 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
S. Yu, "State Complexity: Recent Results and Open Problems", invited talk at ICALP 2004 Formal Language Workshop, also appears in Fundamenta Informaticae 64 (2005) 1–4, 471–480 . 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