World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue: Developments in Language Theory (DLT 2007)No Access

STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES

    https://doi.org/10.1142/S0129054108005838Cited by:19 (Source: Crossref)

    We investigate the state complexity of union and intersection for finite languages. Note that the problem of obtaining the tight bounds for both operations was open. First we compute upper bounds using structural properties of minimal deterministic finite-state automata for finite languages. Then, we show that the upper bounds are tight if we have a variable sized alphabet that can depend on the size of input deterministic finite-state automata. In addition, we prove that the upper bounds are unreachable for any fixed sized alphabet.

    A preliminary version of this paper appeared in Proceedings of 11th International Conference Developments in Language Theory, DLT 2007, Lect. Notes Comput. Sci. 4588, Springer-Verlag, 2007, pp. 217–228.

    References

    • C. Câmpeanuet al., State complexity of basic operations on finite languages, Proceedings of WIA '99, Lecture Notes in Computer Science 2214 (2001) pp. 60–70. Google Scholar
    • T. Claveiroleet al., Lecture Notes in Computer Science 3845 (2006) pp. 116–128. Google Scholar
    • M. Domaratzki, Journal of Automata, Languages and Combinatorics 7(4), 455 (2002). Google Scholar
    • M. Domaratzki and K. Salomaa, Journal of Automata, Languages and Combinatorics 9(3), 217 (2004). ISIGoogle Scholar
    • K. Ellulet al., Journal of Automata, Languages and Combinatorics 9, 233 (2004). ISIGoogle Scholar
    • Y.-S. Han and K. Salomaa, State complexity of basic operations on suffix-free regular languages, Proceedings of MFCS'07, Lecture Notes in Computer Science 4708 (2007) pp. 501–512. Google Scholar
    • Y.-S. Han, K. Salomaa and D. Wood, State complexity of prefix-free regular languages, Proceedings of DCFS'06 (2006) pp. 165–176. Google Scholar
    • M. Holzer and M. Kutrib, Unary language operations and their nondeterministic state complexity, Proceedings of DLT'02, Lecture Notes in Computer Science 2450 (2002) pp. 162–172. Google Scholar
    • M. Holzer and M. Kutrib, International Journal of Foundations of Computer Science 14(6), 1087 (2003), DOI: 10.1142/S0129054103002199. LinkGoogle Scholar
    • J.   Hopcroft and J.   Ullman , Introduction to Automata Theory, Languages, and Computation , 2nd edn. ( Addison-Wesley , Reading, MA , 1979 ) . Google Scholar
    • M. Hricko, G. Jirásková and A. Szabari, Union and intersection of regular languages and descriptional complexity, Proceedings of DCFS'05 (2005) pp. 170–181. Google Scholar
    • J. Jirásek, G. Jirásková and A. Szabari, International Journal of Foundations of Computer Science 16(3), 511 (2005). Link, ISIGoogle Scholar
    • A. Maslov, Soviet Mathematics Doklady 11 (1970) pp. 1373–1375. Google Scholar
    • C. Nicaud, Average state complexity of operations on unary automata, Proceedings of MFCS'99, Lecture Notes in Computer Science 1672 (1999) pp. 231–240. Google Scholar
    • G. Pighizzini and J. Shallit, International Journal of Foundations of Computer Science 13(1), 145 (2002), DOI: 10.1142/S012905410200100X. Link, ISIGoogle Scholar
    • D. R. Raymond and D. Wood, Journal of Symbolic Computation 17, 341 (1994), DOI: 10.1006/jsco.1994.1023. Crossref, ISIGoogle Scholar
    • S. Yu, Handbook of Formal Languages 1, eds. G. Rozenberg and A. Salomaa (Springer-Verlag, 1997) pp. 41–110. CrossrefGoogle Scholar
    • S. Yu, Journal of Automata, Languages and Combinatorics 6(2), 221 (2001). ISIGoogle Scholar
    • S. Yu, Q. Zhuang and K. Salomaa, Theoretical Computer Science 125(2), 315 (1994), DOI: 10.1016/0304-3975(92)00011-F. Crossref, ISIGoogle Scholar
    Remember to check out the Most Cited Articles!

    Check out these Handbooks in Computer Science