Descriptional complexity of error detection

DOI10.1007/978-3-319-46376-6_6MaRDI QIDQ4686648zbMATH OpenOpenAlexFDO

Authors Timothy Ng, David Rappaport, Kai Salomaa

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

zbMATH Keywords

edit distancefinite automatonHausdorff distanceregular languagestate complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• State complexity of neighbourhoods and approximate pattern matching
• State complexity of suffix distance
• State complexity of suffix distance
• State complexity of neighbourhoods and approximate pattern matching
• State complexity of prefix distance of subregular languages

Cites work

• A Second Course in Formal Languages and Automata Theory
• Additive distances and quasi-distances between words
• An algebra of discrete channels that involve combinations of three basic error types
• Bounded repairability of word languages
• Computing maximal error-detecting capabilities and distances of regular languages
• Computing the edit distance of a regular language
• Distances between languages and reflexivity of relations
• Edit distance for pushdown automata
• EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS
• Encyclopedia of Distances
• Error-correction, and finite-delay decodability
• Fast string correction with Levenshtein automata
• Finite transducers and nondeterministic state complexity of regular languages
• Formal descriptions of code properties: decidability, complexity, implementation
• How hard is computing the edit distance?
• scientific article; zbMATH DE number 1250549 (Why is no real title available?)
• scientific article; zbMATH DE number 1024657 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• scientific article; zbMATH DE number 2201366 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• Maximal error-detecting capabilities of formal languages
• Parameterized Prefix Distance between Regular Languages
• Quasi-distances and weighted finite automata
• Quotient Complexity of Ideal Languages
• State complexity of additive weighted finite automata
• State complexity of neighbourhoods and approximate pattern matching
• State complexity of prefix distance
• The edit-distance between a regular language and a context-free language
• The limitedness problem on distance automata: Hashiguchi's method revisited
• The per-character cost of repairing word languages

Cited in

(8)

• Computing maximal error-detecting capabilities and distances of regular languages
• State complexity of neighbourhoods and approximate pattern matching
• State complexity of neighbourhoods and approximate pattern matching
• State complexity of suffix distance
• scientific article; zbMATH DE number 2201366 (Why is no real title available?)
• Edit distance neighbourhoods of input-driven pushdown automata
• Edit distance neighbourhoods of input-driven pushdown automata
• Regularity of a dynamic neighborhood of a regular language

This page was built for publication: Descriptional complexity of error detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4686648)