[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 Pseudocatenation

  • Conference paper
  • First Online:
Language and Automata Theory and Applications (LATA 2019)

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

  • 488 Accesses

Abstract

The state complexity of a regular language \(L_m\) is the number m of states in a minimal deterministic finite automaton (DFA) accepting \(L_m\). The state complexity of a regularity-preserving binary operation on regular languages is defined as the maximal state complexity of the result of the operation, where the two operands range over all languages of state complexities \({\le }m\) and \({\le }n\), respectively. We consider the deterministic and nondeterministic state complexity of pseudocatenation. The pseudocatenation of two words x and y with respect to an antimorphic involution \(\theta \) is the set \(\{xy,x\theta (y)\}\). This operation was introduced in the context of DNA computing as the generator of pseudopowers of words (a pseudopower of a word u is a word in \(u \{u,\theta (u)\}^*\)). We prove that the state complexity of the pseudocatenation of languages \(L_m\) and \(L_n\), where \(m, n \ge 3\), is at most \((m-1)(2^{2n} - 2^{n+1} + 2) + 2^{2n-2} - 2^{n-1} + 1\). Moreover, for \(m, n \ge 3\) there exist languages \(L_m\) and \(L_n\) over an alphabet of size 4, whose pseudocatenation meets the upper bound. We also prove that the state complexity of the positive pseudocatenation closure of a regular language \(L_n\) has an upper bound of \(2^{2n-1} - 2^n +1\), and that this bound can be reached, with the witness being a language over an alphabet of size 4.

This research was supported by the Natural Sciences and Engineering Research Council of Canada Discovery Grant R2824A01, and a University of Waterloo School of Computer Science Grant to L.K.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Brzozowski, J., Liu, D.: Universal witnesses for state complexity of basic operations combined with reversal. In: Konstantinidis, S. (ed.) CIAA 2013. LNCS, vol. 7982, pp. 72–83. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39274-0_8

    Chapter  MATH  Google Scholar 

  2. Brzozowski, J., Liu, D.: Universal witnesses for state complexity of boolean operations and concatenation combined with star. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol. 8031, pp. 30–41. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39310-5_5

    Chapter  MATH  Google Scholar 

  3. Brzozowski, J.A., Kari, L., Li, B., Szykuła, M.: State complexity of overlap assembly. In: Câmpeanu, C. (ed.) CIAA 2018. LNCS, vol. 10977, pp. 109–120. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-94812-6_10

    Chapter  MATH  Google Scholar 

  4. Caron, P., Luque, J.G., Patrou, B.: State complexity of multiple catenation. arXiv:1607.04031 (2016)

  5. Cho, D.J., Han, Y.S., Kim, H., Palioudakis, A., Salomaa, K.: Duplications and pseudo-duplications. Int. J. Unconv. Comput. 12(2–3), 157–168 (2016)

    MATH  Google Scholar 

  6. Cho, D.J., Han, Y.S., Ko, S.K., Salomaa, K.: State complexity of inversion operations. Theoret. Comput. Sci. 610, 2–12 (2016)

    Article  MathSciNet  Google Scholar 

  7. Cui, B., Gao, Y., Kari, L., Yu, S.: State complexity of two combined operations: catenation-union and catenation-intersection. Int. J. Found. Comput. Sci. 22(08), 1797–1812 (2011)

    Article  MathSciNet  Google Scholar 

  8. Cui, B., Gao, Y., Kari, L., Yu, S.: State complexity of combined operations with two basic operations. Theoret. Comput. Sci. 437, 82–102 (2012)

    Article  MathSciNet  Google Scholar 

  9. Cui, B., Gao, Y., Kari, L., Yu, S.: State complexity of two combined operations: catenation-star and catenation-reversal. Int. J. Found. Comput. Sci. 23(01), 51–66 (2012)

    Article  MathSciNet  Google Scholar 

  10. Czeizler, E., Kari, L., Seki, S.: On a special class of primitive words. Theoret. Comput. Sci. 411(3), 617–630 (2010)

    Article  MathSciNet  Google Scholar 

  11. Domaratzki, M., Okhotin, A.: State complexity of power. Theoret. Comput. Sci. 410(24–25), 2377–2392 (2009)

    Article  MathSciNet  Google Scholar 

  12. Gao, Y., Moreira, N., Reis, R., Yu, S.: A survey on operational state complexity. J. Automata Lang. Comb. 21(4), 251–310 (2016)

    MathSciNet  MATH  Google Scholar 

  13. Gao, Y., Yu, S.: State complexity of four combined operations composed of union, intersection, star and reversal. In: Holzer, M., Kutrib, M., Pighizzini, G. (eds.) DCFS 2011. LNCS, vol. 6808, pp. 158–171. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22600-7_13

    Chapter  Google Scholar 

  14. Gao, Y., Yu, S.: State complexity of combined operations with union, intersection, star and reversal. Fundamenta Informaticae 116, 79–92 (2012)

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  16. Kari, L., Konstantinidis, S., Losseva, E., Sosik, P., Thierrin, G.: A formal language analysis of DNA hairpin structures. Fundamenta Informaticae 71, 453–475 (2006)

    MathSciNet  MATH  Google Scholar 

  17. Kari, L., Kulkarni, M.: Generating the pseudo-powers of a word. J. Automata Lang. Comb. 19(1–4), 157–171 (2014)

    MathSciNet  MATH  Google Scholar 

  18. Kari, L., Mahalingam, K.: Watson-Crick conjugate and commutative words. In: Garzon, M.H., Yan, H. (eds.) DNA 2007. LNCS, vol. 4848, pp. 273–283. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-77962-9_29

    Chapter  MATH  Google Scholar 

  19. Kari, L., Seki, S.: On pseudoknot-bordered words and their properties. J. Comput. Syst. Sci. 75, 113–121 (2009)

    Article  MathSciNet  Google Scholar 

  20. Liu, G., Martin-Vide, C., Salomaa, A., Yu, S.: State complexity of basic language operations combined with reversal. Inf. Comput. 206(9–10), 1178–1186 (2008)

    Article  MathSciNet  Google Scholar 

  21. de Luca, A., Luca, A.D.: Pseudopalindrome closure operators in free monoids. Theoret. Comput. Sci. 362(1–3), 282–300 (2006)

    Article  MathSciNet  Google Scholar 

  22. Rampersad, N.: The state complexity of \(L^2\) and \(L^k\). Inf. Process. Lett. 98(6), 231–234 (2006)

    Article  Google Scholar 

  23. Salomaa, A., Salomaa, K., Yu, S.: State complexity of combined operations. Theoret. Comput. Sci. 383(2–3), 140–152 (2007)

    Article  MathSciNet  Google Scholar 

  24. Salomaa, A., Salomaa, K., Yu, S.: Undecidability of state complexity. Int. J. Comput. Math. 90(6), 1310–1320 (2013)

    Article  MathSciNet  Google Scholar 

  25. Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 41–110. Springer, Heidelberg (1997). https://doi.org/10.1007/978-3-642-59136-5_2

    Chapter  Google Scholar 

  26. Yu, S., Salomaa, K., Zhuang, Q.: The state complexities of some basic operations on regular languages. Theoret. Comput. Sci. 125(2), 315–328 (1994)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Science, University of Waterloo, Waterloo, ON, N2L 3G1, Canada

    Lila Kari & Timothy Ng

Authors
  1. Lila Kari
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Timothy Ng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Timothy Ng .

Editor information

Editors and Affiliations

  1. Rovira i Virgili University, Tarragona, Spain

    Carlos Martín-Vide

  2. Saint Petersburg State University, St. Petersburg, Russia

    Alexander Okhotin

  3. Ariel University, Ariel, Israel

    Dana Shapira

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Kari, L., Ng, T. (2019). State Complexity of Pseudocatenation. In: Martín-Vide, C., Okhotin, A., Shapira, D. (eds) Language and Automata Theory and Applications. LATA 2019. Lecture Notes in Computer Science(), vol 11417. Springer, Cham. https://doi.org/10.1007/978-3-030-13435-8_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-13435-8_15

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-13434-1

  • Online ISBN: 978-3-030-13435-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation