State Complexity of Suffix Distance

DOI10.1142/S0129054119400355zbMath1427.68151OpenAlexW4252967799MaRDI QIDQ5205049

Kai Salomaa, Timothy Ng, David Rappaport

Publication date: 10 December 2019

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

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

zbMATH Keywords

regular languagesstate complexityfinite languagessuffix distance

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Descriptional and computational complexity of finite automata -- a survey
• Distances between languages and reflexivity of relations
• Quotient complexity of closed languages
• Efficient algorithms for computing the inner edit distance of a regular language via transducers
• State complexity of prefix distance
• Computing the edit distance of a regular language
• Parameterized Prefix Distance between Regular Languages
• String distances and intrusion detection: Bridging the gap between formal languages and computer security
• A Second Course in Formal Languages and Automata Theory
• State Complexity of Neighbourhoods and Approximate Pattern Matching
• Descriptional Complexity of Error Detection
• THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE
• Encyclopedia of Distances
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: State Complexity of Suffix Distance