Efficient algorithms for computing the inner edit distance of a regular language via transducers (Q1712004)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficient algorithms for computing the inner edit distance of a regular language via transducers |
scientific article |
Statements
Efficient algorithms for computing the inner edit distance of a regular language via transducers (English)
0 references
21 January 2019
0 references
Summary: 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).
0 references
algorithms
0 references
automata
0 references
complexity
0 references
edit distance
0 references
implementation
0 references
transducers
0 references
regular language
0 references
0 references