Descriptional Complexity of Error Detection
From MaRDI portal
Publication:4686648
DOI10.1007/978-3-319-46376-6_6zbMath1396.68068OpenAlexW2547353811MaRDI QIDQ4686648
David Rappaport, Kai Salomaa, Timothy Ng
Publication date: 4 October 2018
Published in: Emergent Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-46376-6_6
Related Items
State Complexity of Suffix Distance, Edit distance neighbourhoods of input-driven pushdown automata, Edit distance neighbourhoods of input-driven pushdown automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bounded repairability of word languages
- Fast string correction with Levenshtein automata
- Distances between languages and reflexivity of relations
- How hard is computing the edit distance?
- An algebra of discrete channels that involve combinations of three basic error types
- The limitedness problem on distance automata: Hashiguchi's method revisited
- Finite transducers and nondeterministic state complexity of regular languages
- Computing the edit distance of a regular language
- The per-character cost of repairing word languages
- FORMAL DESCRIPTIONS OF CODE PROPERTIES: DECIDABILITY, COMPLEXITY, IMPLEMENTATION
- Parameterized Prefix Distance between Regular Languages
- State Complexity of Prefix Distance
- Computing Maximal Error-detecting Capabilities and Distances of Regular Languages
- STATE COMPLEXITY OF ADDITIVE WEIGHTED FINITE AUTOMATA
- Edit Distance for Pushdown Automata
- State Complexity of Neighbourhoods and Approximate Pattern Matching
- A Second Course in Formal Languages and Automata Theory
- Quotient Complexity of Ideal Languages
- THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE
- Quasi-Distances and Weighted Finite Automata
- EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS
- Encyclopedia of Distances
