Abstract
The neighbourhood of a language L with respect to an additive distance consists of all strings that have distance at most the given radius from some string of L. We show that the worst case (deterministic) state complexity of a radius r neighbourhood of a language recognized by an n state nondeterministic finite automaton A is \((r+2)^n\). The lower bound construction uses an alphabet of size linear in n. We show that the worst case state complexity of the set of strings that contain a substring within distance r from a string recognized by A is \((r+2)^{n-2} + 1\).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bordihn, H., Holzer, M., Kutrib, M.: Determination of finite automata accepting subregular languages. Theoretical Computer Science 410, 3209–3249 (2009)
Boyer, R.S., Moore, J.S.: A fast string searching algorithm. Communications of ACM 20, 762–772 (1977)
Brzozowski, J., Jirásková, G., Li, B.: Quotient complexity of ideal languages. In: López-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 208–221. Springer, Heidelberg (2010)
Calude, C.S., Salomaa, K., Yu, S.: Additive Distances and Quasi-Distances Between Words. Journal of Universal Computer Science 8(2), 141–152 (2002)
Deza, M.M., Deza, E.: Encyclopedia of Distances. Springer-Verlag, Heidelberg (2009)
El-Mabrouk, N.: On the size of minimal automata for approximate string matching. Technical report, Institut Gaspard Monge, Université de Marne la Vallée, Paris (1997)
Han, Y.-S., Ko, S.-K., Salomaa, K.: The edit distance between a regular language and a context-free language. International Journal of Foundations of Computer Science 24, 1067–1082 (2013)
Kari, L., Konstantinidis, S.: Descriptional complexity of error/edit systems. Journal of Automata, Languages, and Combinatorics 9, 293–309 (2004)
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)
Konstantinidis, S.: Transducers and the properties of error detection, error-correction, and finite-delay decodability. Journal of Universal Computer Science 8, 278–291 (2002)
Konstantinidis, S.: Computing the edit distance of a regular language. Information and Computation 205, 1307–1316 (2007)
Konstantinidis, S., Silva, P.: Maximal error-detecting capabilities of formal languages. J. Automata, Languages and Combinatorics 13, 55–71 (2008)
Konstantinidis, S., Silva, P.: Computing maximal error-detecting capabilities and distances of regular languages. Fundamenta Informaticae 101, 257–270 (2010)
Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady 10(8), 707–710 (1966)
Ng, T., Rappaport, D., Salomaa, K.: Quasi-distances and weighted finite automata. In: Shallit, J., Okhotin, A. (eds.) DCFS 2015. LNCS, vol. 9118, pp. 209–219. Springer, Heidelberg (2015)
Pighizzini, G.: How hard is computing the edit distance? Information and Computation 165, 1–13 (2001)
Povarov, G.: Descriptive complexity of the hamming neighborhood of a regular language. In: Language and Automata Theory and Applications, pp. 509–520 (2007)
Salomaa, K., Schofield, P.: State Complexity of Additive Weighted Finite Automata. International Journal of Foundations of Computer Science 18(06), 1407–1416 (2007)
Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press (2009)
Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (Eds.) Handbook of Formal Languages, vol. I, pp. 41–110. Springer (1997)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Ng, T., Rappaport, D., Salomaa, K. (2015). State Complexity of Neighbourhoods and Approximate Pattern Matching. In: Potapov, I. (eds) Developments in Language Theory. DLT 2015. Lecture Notes in Computer Science(), vol 9168. Springer, Cham. https://doi.org/10.1007/978-3-319-21500-6_31
Download citation
DOI: https://doi.org/10.1007/978-3-319-21500-6_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21499-3
Online ISBN: 978-3-319-21500-6
eBook Packages: Computer ScienceComputer Science (R0)