Efficient Algorithms for Computing the Inner Edit Distance of a Regular Language via Transducers
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 Nondetermini...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2018-10-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/11/11/165 |
| _version_ | 1811332686121271296 |
|---|---|
| author | Lila Kari Stavros Konstantinidis Steffen Kopecki Meng Yang |
| author_facet | Lila Kari Stavros Konstantinidis Steffen Kopecki Meng Yang |
| author_sort | Lila Kari |
| collection | DOAJ |
| description | 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 <inline-formula> <math display="inline"> <semantics> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>r</mi> <mn>2</mn> </msup> <msup> <mi>n</mi> <mn>2</mn> </msup> <mi>d</mi> <mo stretchy="false">)</mo> </mrow> </semantics> </math> </inline-formula>, where <i>r</i> is the cardinality of the alphabet involved, <i>n</i> is the number of transitions in the given NFA, and <i>d</i> 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). |
| first_indexed | 2024-04-13T16:40:42Z |
| format | Article |
| id | doaj.art-28377fedee3d48e3aa1831e44380f44c |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-04-13T16:40:42Z |
| publishDate | 2018-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-28377fedee3d48e3aa1831e44380f44c2022-12-22T02:39:14ZengMDPI AGAlgorithms1999-48932018-10-01111116510.3390/a11110165a11110165Efficient Algorithms for Computing the Inner Edit Distance of a Regular Language via TransducersLila Kari0Stavros Konstantinidis1Steffen Kopecki2Meng Yang3School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, CanadaDepartment of Mathematics and Computing Science, Saint Mary’s University, Halifax, NS B3H 3C3, CanadaDepartment of Mathematics and Computing Science, Saint Mary’s University, Halifax, NS B3H 3C3, CanadaDepartment of Mathematics and Computing Science, Saint Mary’s University, Halifax, NS B3H 3C3, CanadaThe 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 <inline-formula> <math display="inline"> <semantics> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>r</mi> <mn>2</mn> </msup> <msup> <mi>n</mi> <mn>2</mn> </msup> <mi>d</mi> <mo stretchy="false">)</mo> </mrow> </semantics> </math> </inline-formula>, where <i>r</i> is the cardinality of the alphabet involved, <i>n</i> is the number of transitions in the given NFA, and <i>d</i> 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).https://www.mdpi.com/1999-4893/11/11/165algorithmsautomatacomplexityedit distanceimplementationtransducersregular language |
| spellingShingle | Lila Kari Stavros Konstantinidis Steffen Kopecki Meng Yang Efficient Algorithms for Computing the Inner Edit Distance of a Regular Language via Transducers Algorithms algorithms automata complexity edit distance implementation transducers regular language |
| title | Efficient Algorithms for Computing the Inner Edit Distance of a Regular Language via Transducers |
| title_full | Efficient Algorithms for Computing the Inner Edit Distance of a Regular Language via Transducers |
| title_fullStr | Efficient Algorithms for Computing the Inner Edit Distance of a Regular Language via Transducers |
| title_full_unstemmed | Efficient Algorithms for Computing the Inner Edit Distance of a Regular Language via Transducers |
| title_short | Efficient Algorithms for Computing the Inner Edit Distance of a Regular Language via Transducers |
| title_sort | efficient algorithms for computing the inner edit distance of a regular language via transducers |
| topic | algorithms automata complexity edit distance implementation transducers regular language |
| url | https://www.mdpi.com/1999-4893/11/11/165 |
| work_keys_str_mv | AT lilakari efficientalgorithmsforcomputingtheinnereditdistanceofaregularlanguageviatransducers AT stavroskonstantinidis efficientalgorithmsforcomputingtheinnereditdistanceofaregularlanguageviatransducers AT steffenkopecki efficientalgorithmsforcomputingtheinnereditdistanceofaregularlanguageviatransducers AT mengyang efficientalgorithmsforcomputingtheinnereditdistanceofaregularlanguageviatransducers |