Efficient algorithms for computing the inner edit distance of a regular language via transducers
From MaRDI portal
Publication:1712004
DOI10.3390/a11110165zbMath1461.68102OpenAlexW2898086057WikidataQ129080311 ScholiaQ129080311MaRDI QIDQ1712004
Meng Yang, Lila Kari, Steffen Kopecki, Stavros Konstantinidis
Publication date: 21 January 2019
Published in: Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.3390/a11110165
Related Items (5)
State Complexity of Neighbourhoods and Approximate Pattern Matching ⋮ State Complexity of Prefix Distance ⋮ Finite Approximations and Similarity of Languages ⋮ State Complexity of Neighbourhoods and Approximate Pattern Matching ⋮ State Complexity of Suffix Distance
Uses Software
Cites Work
- siEDM: an efficient string index and search algorithm for edit distance with moves
- Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- How hard is computing the edit distance?
- Computing the edit distance of a regular language
- Applications of transducers in independent languages, word distances, codes
- Prefix Distance Between Regular Languages
- Computing Maximal Error-detecting Capabilities and Distances of Regular Languages
- The Cost of Traveling between Languages
- Computing the Edit-Distance between a Regular Language and a Context-Free Language
- Algorithms on Strings, Trees and Sequences
- Order- n correction for regular languages
- Approximate Matching between a Context-Free Grammar and a Finite-State Automaton
- Insertion/Deletion Detecting Codes and the Boundary Problem
- EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Efficient algorithms for computing the inner edit distance of a regular language via transducers
