{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:05:28Z","timestamp":1760241928715,"version":"build-2065373602"},"reference-count":30,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2018,10,23]],"date-time":"2018-10-23T00:00:00Z","timestamp":1540252800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The concept of edit distance and its variants has applications in many areas such as computational linguistics, bioinformatics, and synchronization error detection in data communications. Here, we revisit the problem of computing the inner edit distance of a regular language given via a Nondeterministic Finite Automaton (NFA). This problem relates to the inherent maximal error-detecting capability of the language in question. We present two efficient algorithms for solving this problem, both of which execute in time     O (  r 2   n 2  d )    , where r is the cardinality of the alphabet involved, n is the number of transitions in the given NFA, and d is the computed edit distance. We have implemented one of the two algorithms and present here a set of performance tests. The correctness of the algorithms is based on the connection between word distances and error detection and the fact that nondeterministic transducers can be used to represent the errors (resp., edit operations) involved in error-detection (resp., in word distances).<\/jats:p>","DOI":"10.3390\/a11110165","type":"journal-article","created":{"date-parts":[[2018,10,24]],"date-time":"2018-10-24T02:59:40Z","timestamp":1540349980000},"page":"165","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Algorithms for Computing the Inner Edit Distance of a Regular Language via Transducers"],"prefix":"10.3390","volume":"11","author":[{"given":"Lila","family":"Kari","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stavros","family":"Konstantinidis","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computing Science, Saint Mary\u2019s University, Halifax, NS B3H 3C3, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steffen","family":"Kopecki","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computing Science, Saint Mary\u2019s University, Halifax, NS B3H 3C3, Canada"},{"name":"Department of Computer Science, University of Western Ontario, London, ON N6A 5B7, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meng","family":"Yang","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computing Science, Saint Mary\u2019s University, Halifax, NS B3H 3C3, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,10,23]]},"reference":[{"key":"ref_1","unstructured":"Sankoff, D., and Kruskal, J.B. (1999). Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, CSLI Publications."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press.","DOI":"10.1017\/CBO9780511574931"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"5935","DOI":"10.1109\/TIT.2013.2264825","article-title":"Insertion\/deletion detecting codes and the boundary problem","volume":"59","author":"Paluncic","year":"2013","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1307","DOI":"10.1016\/j.ic.2007.06.001","article-title":"Computing the edit distance of a regular language","volume":"205","author":"Konstantinidis","year":"2007","journal-title":"Inf. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"257","DOI":"10.3233\/FI-2010-287","article-title":"Computing maximal error-detecting capabilities and distances of regular languages","volume":"101","author":"Konstantinidis","year":"2010","journal-title":"Fundam. Inform."},{"key":"ref_6","first-page":"117","article-title":"Efficient algorithms for testing the twins property","volume":"8","author":"Allauzen","year":"2003","journal-title":"J. Autom. Lang. Comb."},{"key":"ref_7","unstructured":"FAdo (2018, October 20). Tools for Formal Languages Manipulation. Available online: http:\/\/fado.dcc.fc.up.pt\/."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1145\/360980.360995","article-title":"Order-n correction for regular languages","volume":"17","author":"Wagner","year":"1974","journal-title":"Commun. ACM"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/inco.2000.2914","article-title":"How hard is computing the edit distance?","volume":"165","author":"Pighizzini","year":"2001","journal-title":"Inf. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1142\/S0129054103002114","article-title":"Edit-distance of weighted automata: General definitions and algorithms","volume":"14","author":"Mohri","year":"2003","journal-title":"Intern. J. Found. Comput. Sci."},{"key":"ref_11","unstructured":"Kari, L., Konstantinidis, S., Perron, S., Wozniak, G., and Xu, J. (2003). Finite-State Error\/Edit-Systems and Difference- Measures for Languages and Words, Mathematics and Computing Science, Saint Mary\u2019s University. Report 2003-01."},{"key":"ref_12","unstructured":"Aceto, L., Henziger, M., and Sgall, J. (2011). The cost of traveling between languages. ICALP 2011, Part II. LNCS 6756, Springer."},{"key":"ref_13","unstructured":"Yen, H.C., and Ibarra, O. (2012). Computing the edit-distance between a regular language and a context-free langauge. DLT 2012. LNCS 7410, Springer."},{"key":"ref_14","unstructured":"Konstantinidis, S. (2013). Approximate matching between a context-free grammar and a finite-state automaton. CIAA 2013. LNCS 7982, Springer."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Takabatake, Y., Nakashima, K., Kuboyama, T., Tabei, Y., and Sakamoto, H. (2016). siEDM: An Efficient String Index and Search Algorithm for Edit Distance with Moves. Algorithms, 9.","DOI":"10.3390\/a9020026"},{"key":"ref_16","unstructured":"Ng, T. (2016, January 19\u201322). Prefix Distance Between Regular Languages. Proceedings of the 21st CIAA, Seoul, South Korea."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Berstel, J. (1979). Transductions and Context-Free Languages, B.G. Teubner.","DOI":"10.1007\/978-3-663-09367-1"},{"key":"ref_18","unstructured":"Wood, D. (1987). Theory of Computation, John Wiley & Sons."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Rozenberg, G., and Salomaa, A. (1997). Handbook of Formal Languages, Vol. I, Springer.","DOI":"10.1007\/978-3-642-59126-6"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Yu, S. (1997). Regular Languages. Handbook of Formal Languages, Vol. I, Springer.","DOI":"10.1007\/978-3-642-59136-5_2"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Sakarovitch, J. (2009). Elements of Automata Theory, Cambridge University Press.","DOI":"10.1017\/CBO9781139195218"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Mateescu, A., and Salomaa, A. (1997). Formal Languages: an Introduction and a Synopsis. Handbook of Formal Languages, Vol. I, Springer.","DOI":"10.1007\/978-3-642-59136-5_1"},{"key":"ref_23","first-page":"293","article-title":"Descriptional Complexity of Error\/Edit Systems","volume":"9","author":"Kari","year":"2004","journal-title":"J. Autom. Lang. Comb."},{"key":"ref_24","first-page":"707","article-title":"Binary Codes Capable of Correcting Deletions, Insertions, and Reversals","volume":"10","author":"Levenshtein","year":"1966","journal-title":"Sov. Phys. Dokl."},{"key":"ref_25","unstructured":"Yang, M. (2012). Application and Implementation of Transducer Tools in Answering Certain Questions about Regular Languages. [Master\u2019s Thesis, Department Mathematics and Computing Science, Saint Mary\u2019s University]."},{"key":"ref_26","unstructured":"Schrijver, A. (2003). Combinatorial Optimization: Polyhedra and Efficiency, Springer Science & Business Media."},{"key":"ref_27","first-page":"278","article-title":"Transducers and the Properties of Error-Detection, Error-Correction and Finite-Delay Decodability","volume":"8","author":"Konstantinidis","year":"2002","journal-title":"J. Univ. Comput. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/S0304-3975(01)00214-6","article-title":"Squaring transducers: An efficient procedure for deciding functionality and sequentiality","volume":"292","author":"Carton","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Shyr, H., and Thierrin, G. (1975). Codes and Binary Relations. S\u00e9minaire d\u2019Alg\u00e8bre Paul Dubreil, Paris 1975\u20131976 (29\u00e8me Ann\u00e9e), Springer. Lecture Notes in Mathematics.","DOI":"10.1007\/BFb0087133"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Konstantinidis, S. (2017, January 3\u20135). Applications of Transducers in Independent Languages, Word Distances, Codes. Proceedings of the DCFS 2017, Milano, Italy.","DOI":"10.1007\/978-3-319-60252-3_4"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/11\/165\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:25:43Z","timestamp":1760196343000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/11\/165"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,23]]},"references-count":30,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2018,11]]}},"alternative-id":["a11110165"],"URL":"https:\/\/doi.org\/10.3390\/a11110165","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2018,10,23]]}}}