State Complexity of Suffix Distance | SpringerLink
Skip to main content
Springer Nature Link
Log in

State Complexity of Suffix Distance

  • Conference paper
  • First Online:
Descriptional Complexity of Formal Systems (DCFS 2017)

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

Included in the following conference series:

  • 330 Accesses

Abstract

The neighbourhood of a regular language with respect to the prefix, suffix and subword distance is always regular and a tight bound for the state complexity of prefix distance neighbourhoods is known. We give upper bounds for the state complexity of the neighbourhood of radius k of an n state DFA (deterministic finite automaton) language with respect to the suffix distance and the subword distance, respectively. For restricted values of k and n we give a matching lower bound for the state complexity of suffix distance neighbourhoods.

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
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • 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., Jirásková, G., Zou, C.: Quotient complexity of closed languages. Theory Comput. Syst. 54(2), 277–292 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  2. Calude, C.S., Salomaa, K., Yu, S.: Additive distances and quasi-distances between words. J. Univers. Comput. Sci. 8(2), 141–152 (2002)

    MathSciNet  MATH  Google Scholar 

  3. Choffrut, C., Pighizzini, G.: Distances between languages and reflexivity of relations. Theoret. Comput. Sci. 286(1), 117–138 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  4. Deza, M.M., Deza, E.: Encyclopedia of Distances. Springer, Heidelberg (2009)

    Book  MATH  Google Scholar 

  5. Gao, Y., Moreira, N., Reis, R., Yu, S.: A survey on operational state complexity. To appear in Computer Science Review, September 2015. arXiv:1509.03254v1 [cs.FL]

  6. Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata—a survey. Inf. Comput. 209, 456–470 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  7. Han, Y.-S., Ko, S.-K., Salomaa, K.: The edit distance between a regular language and a context-free language. Int. J. Found. Comput. Sci. 24, 1067–1082 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  8. Kari, L., Konstantinidis, S.: Descriptional complexity of error/edit systems. J. Automata Lang. Comb. 9, 293–309 (2004)

    MathSciNet  MATH  Google Scholar 

  9. Kari, L., Konstantinidis, S., Kopecki, S., Yang, M.: An efficient algorithm for computing the edit distance of a regular language via input-altering transducers. CoRR abs/1406.1041 (2014)

    Google Scholar 

  10. Konstantinidis, S.: Computing the edit distance of a regular language. Inf. Comput. 205, 1307–1316 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  11. Kutrib, M., Meckel, K., Wendlandt, M.: Parameterized prefix distance between regular languages. In: Geffert, V., Preneel, B., Rovan, B., Štuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 419–430. Springer, Cham (2014). doi:10.1007/978-3-319-04298-5_37

    Chapter  Google Scholar 

  12. Kutrib, M., Pighizzini, G.: Recent trends in descriptional complexity of formal languages. Bull. EATCS 111, 70–86 (2013)

    MathSciNet  Google Scholar 

  13. Lothaire, M.: Algorithms on words. In: Applied Combinatorics on Words. Encyclopedia of Mathematics and it’s Applications, vol. 105. Cambridge University Press, New York (2005)

    Google Scholar 

  14. Ng, T., Rappaport, D., Salomaa, K.: State complexity of neighbourhoods and approximate pattern matching. In: Potapov, I. (ed.) DLT 2015. LNCS, vol. 9168, pp. 389–400. Springer, Cham (2015). doi:10.1007/978-3-319-21500-6_31

    Chapter  Google Scholar 

  15. Ng, T., Rappaport, D., Salomaa, K.: State complexity of prefix distance. In: Drewes, F. (ed.) CIAA 2015. LNCS, vol. 9223, pp. 238–249. Springer, Cham (2015). doi:10.1007/978-3-319-22360-5_20

    Chapter  Google Scholar 

  16. Ng, T., Rappaport, D., Salomaa, K.: State complexity of prefix distance of subregular languages. In: Câmpeanu, C., Manea, F., Shallit, J. (eds.) DCFS 2016. LNCS, vol. 9777, pp. 192–204. Springer, Cham (2016). doi:10.1007/978-3-319-41114-9_15

    Chapter  Google Scholar 

  17. Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, Cambridge (2009)

    MATH  Google Scholar 

  18. Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 41–110. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

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

    Timothy Ng, David Rappaport & Kai Salomaa

Authors
  1. Timothy Ng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David Rappaport
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kai Salomaa
    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. Università degli Studi di Milano, Milan, Italy

    Giovanni Pighizzini

  2. University of Prince Edward Island, Charlottetown, Prince Edward Island, Canada

    Cezar Câmpeanu

Rights and permissions

Reprints and permissions

Copyright information

© 2017 IFIP International Federation for Information Processing

About this paper

Cite this paper

Ng, T., Rappaport, D., Salomaa, K. (2017). State Complexity of Suffix Distance. In: Pighizzini, G., Câmpeanu, C. (eds) Descriptional Complexity of Formal Systems. DCFS 2017. Lecture Notes in Computer Science(), vol 10316. Springer, Cham. https://doi.org/10.1007/978-3-319-60252-3_23

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-60252-3_23

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-60251-6

  • Online ISBN: 978-3-319-60252-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation