State Complexity of Neighbourhoods and Approximate Pattern Matching

DOI10.1142/S0129054118400099zbMath1387.68159OpenAlexW2797999682MaRDI QIDQ4640043

Kai Salomaa, Timothy Ng, David Rappaport

Publication date: 15 May 2018

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054118400099

zbMATH Keywords

lower boundsregular languagesstate complexityadditive distance

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

Computing the Shortest String and the Edit-Distance for Parsing Expression Languages ⋮ Weak inverse neighborhoods of languages ⋮ Closest substring problems for regular languages ⋮ State Complexity of Suffix Distance ⋮ Input-driven pushdown automata for edit distance neighborhood ⋮ Edit distance neighbourhoods of input-driven pushdown automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounded repairability of word languages
• Fast string correction with Levenshtein automata
• Efficient algorithms for computing the inner edit distance of a regular language via transducers
• How hard is computing the edit distance?
• Determination of finite automata accepting subregular languages
• Computing the edit distance of a regular language
• Computing Maximal Error-detecting Capabilities and Distances of Regular Languages
• A fast string searching algorithm
• STATE COMPLEXITY OF ADDITIVE WEIGHTED FINITE AUTOMATA
• 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
• Encyclopedia of Distances

This page was built for publication: State Complexity of Neighbourhoods and Approximate Pattern Matching