[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

State Complexity of Nested Word Automata

  • Conference paper
Language and Automata Theory and Applications (LATA 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5457))

Abstract

We discuss techniques to establish lower bounds for the number of states of finite automata operating on nested words. To illustrate these methods we establish a lower bound for the state complexity of Kleene star that is of a different order than the known tight state complexity bound for the star of ordinary regular languages. We survey known bounds on deterministic and nondeterministic state complexity of basic operations on regular nested word languages and discuss open problems.

Research supported by the Natural Sciences and Engineering ResearchCouncil of Canada.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Alur, R.: Marrying words and trees. In: Proc. of 26th ACM Symposium on Principles of Database Systems, PODS 2007, pp. 233–242 (2007)

    Google Scholar 

  2. Alur, R., Arenas, M., Barceló, P., Etessami, K., Immerman, N., Libkin, L.: First-order and temporal logics for nested words. In: Proc. of 22nd IEEE Symposium on Logic in Computer Science, pp. 151–160 (2007)

    Google Scholar 

  3. Alur, R., Kumar, V., Madhusudan, P., Viswanathan, M.: Congruences for visibly pushdown languages. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1102–1114. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  4. Alur, R., Madhusudan, P.: Adding nesting structure to words. In: H. Ibarra, O., Dang, Z. (eds.) DLT 2006. LNCS, vol. 4036, pp. 1–13. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  5. Alur, R., Madhusudan, P.: Adding nesting structure to words. Full version of [4], www.cis.upenn.edu/~alur/Stoc04Dlt06.pdf

  6. Arenas, M., Barceló, P., Libkin, L.: Regular languages of nested words: Fixed points, automata, and synchronization. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 888–900. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  7. Birget, J.C.: Intersection and union of regular languages and state complexity. Inform. Process. Lett. 43, 185–190 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chervet, P., Walukiewicz, I.: Minimizing variants of visibly pushdown automata. In: Kučera, L., Kučera, A. (eds.) MFCS 2007. LNCS, vol. 4708, pp. 135–146. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  9. Domaratzki, M., Salomaa, K.: Lower bounds for the transition complexity of NFAs. J. Comput. System. Sci. 74, 1116–1130 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  10. Domaratzki, M., Salomaa, K.: Transition complexity of language operations. Theoret. Comput. Sci. 387, 147–154 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  11. Gao, Y., Salomaa, K., Yu, S.: The state complexity of two combined operations: Star of catenation and star of reversal. Fund. Inform. 83, 75–89 (2008)

    MathSciNet  MATH  Google Scholar 

  12. Gauwin, O., Niehren, J., Roos, Y.: Streaming tree automata. Inform. Proc. Lett. 109, 13–17 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  13. Gécseg, F., Steinby, M.: Tree languages. In: [27], vol. III, pp. 1–68

    Google Scholar 

  14. Glaister, I., Shallit, J.: A lower bound technique for the size of nondeterministic finite automata. Inform. Process. Lett. 59, 75–77 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  15. Goldstine, J., Kappes, M., Kintala, C.M.R., Leung, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. J. Universal Comput. Sci. 8, 193–234 (2002)

    MathSciNet  MATH  Google Scholar 

  16. Gruber, H., Holzer, M.: Finding lower bounds for nondeterministic state complexity is hard. In: H. Ibarra, O., Dang, Z. (eds.) DLT 2006. LNCS, vol. 4036, pp. 363–374. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  17. Gruber, H., Holzer, M.: Inapproximability of nondeterministic state and transition complexity assuming P ≠ NP. In: Harju, T., Karhumäki, J., Lepistö, A. (eds.) DLT 2007. LNCS, vol. 4588, pp. 205–216. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  18. Han, Y.-S., Salomaa, K.: Nondeterministic state complexity of nested word automata (September 2008) (submitted for publication)

    Google Scholar 

  19. Holzer, M., Kutrib, M.: Nondeterministic descriptional complexity of regular languages. Internat. J. Foundations of Comput. Sci. 14, 1087–1102 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  20. Hromkovič, J.: Communication Complexity and Parallel Computing. Springer, Heidelberg (1997)

    Book  MATH  Google Scholar 

  21. Hromkovič, J.: Descriptional complexity of finite automata: Concepts and open problems. J. Automata, Languages and Combinatorics 7, 519–531 (2002)

    MathSciNet  MATH  Google Scholar 

  22. Jirásková, G.: State complexity of some operations on binary regular languages. Theoret. Comput. Sci. 330, 287–298 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  23. Kumar, V., Madhusudan, P., Viswanathan, M.: Minimization, learning, and conformance testing of boolean programs. In: Baier, C., Hermanns, H. (eds.) CONCUR 2006. LNCS, vol. 4137, pp. 203–217. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  24. Piao, X., Salomaa, K.: Operational state complexity of nested word automata. In: Câmpeanu, C., Pighizzini, G. (eds.) Descriptional Complexity of Formal Systems, DCFS 2008, Charlottetown, Canada, pp. 194–206 (2008)

    Google Scholar 

  25. Neumann, A., Seidl, H.: Locating matches of tree patterns in forests. In: Arvind, V., Ramanujam, R. (eds.) FST TCS 1998. LNCS, vol. 1530, pp. 134–146. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  26. Nguyen, H.: VPAlib: Visibly pushdown automata library (2006), http://www.emn.fr/x-info/hnguyen/vpa

  27. Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, vol. I–III. Springer, Heidelberg (1997)

    MATH  Google Scholar 

  28. Salomaa, K., Yu, S.: On the state complexity of combined operations and their estimation. Internat. J. Foundations of Comput. Sci. 18, 683–698 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  29. Yu, S.: Regular languages. In: [27], vol. I, pp. 41–110

    Google Scholar 

  30. Yu, S.: Grail+: A symbolic computation environment for finite-state machines, regular expressions and finite languages (2002), http://www.csd.uwo.ca/Research/grail

  31. Yu, S.: State complexity: Recent results and open problems. Fund. Inform. 64, 471–480 (2005)

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computing, Queen’s University, Kingston, Ontario, K7L 3N6, Canada

    Kai Salomaa

Authors
  1. Kai Salomaa
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Research Group on Mathematical Linguistics, Rovira i Virgili University, Av. Catalunya, 35, 43002, Tarragona, Spain

    Adrian Horia Dediu

  2. Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona, Spain

    Armand Mihai Ionescu

  3. European Research Council Executive Agency, 16 Place Rogier, 1210, Brussels, Belgium

    Carlos Martín-Vide

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Salomaa, K. (2009). State Complexity of Nested Word Automata. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (eds) Language and Automata Theory and Applications. LATA 2009. Lecture Notes in Computer Science, vol 5457. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00982-2_5

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-00982-2_5

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-00981-5

  • Online ISBN: 978-3-642-00982-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation