State Complexity of Neighbourhoods and Approximate Pattern Matching

DOI10.1007/978-3-319-21500-6_31zbMath1386.68096OpenAlexW2293608128MaRDI QIDQ3451118

David Rappaport, Timothy Ng, Kai Salomaa

Publication date: 10 November 2015

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1974/24211

zbMATH Keywords

lower boundsregular languagesstate complexityadditive distance

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (5)

Consensus String Problem for Multiple Regular Languages ⋮ Descriptional Complexity of Error Detection ⋮ Consensus string problem for multiple regular languages ⋮ Quasi-Distances and Weighted Finite Automata ⋮ State complexity of prefix distance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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