Efficient algorithms for computing the inner edit distance of a regular language via transducers
type: Item
instance of: scholarly article
title: Efficient algorithms for computing the inner edit distance of a regular language via transducers
zbMATH Open document ID: 1461.68102
author: Lila Kari
author: Stavros Konstantinidis
author: Steffen Kopecki
author: Meng Yang
published in: Algorithms
publication date: 2019-01-21T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 7003816
zbMATH Keywords: algorithms
zbMATH Keywords: automata
zbMATH Keywords: complexity
zbMATH Keywords: edit distance
zbMATH Keywords: implementation
zbMATH Keywords: transducers
zbMATH Keywords: regular language
describes a project that uses: siEDM
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a11110165
OpenAlex ID: W2898086057
cites work: Q4509227
cites work: Algorithms on Strings, Trees and Sequences
cites work: Insertion/Deletion Detecting Codes and the Boundary Problem
cites work: Computing the edit distance of a regular language
cites work: Computing Maximal Error-detecting Capabilities and Distances of Regular Languages
cites work: Q4449534
cites work: Order- n correction for regular languages
cites work: How hard is computing the edit distance?
cites work: EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS
cites work: The Cost of Traveling between Languages
cites work: Computing the Edit-Distance between a Regular Language and a Context-Free Language
cites work: Approximate Matching between a Context-Free Grammar and a Finite-State Automaton
cites work: siEDM: an efficient string index and search algorithm for edit distance with moves
cites work: Prefix Distance Between Regular Languages
cites work: Q3859267
cites work: Q4692941
cites work: Q4714446
cites work: Q3644388
cites work: Q5313794
cites work: Q5528329
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: Q5422240
cites work: Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
cites work: Applications of transducers in independent languages, word distances, codes
Wikidata QID: Q129080311
DOI: 10.3390/A11110165
description: scientific article; zbMATH DE number 7003816