State complexity of suffix distance

DOI10.1142/S0129054119400355MaRDI QIDQ5205049zbMATH OpenOpenAlexFDO

Authors Timothy Ng, David Rappaport, Kai Salomaa

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)

Recommendations

• State complexity of suffix distance
• State complexity of prefix distance of subregular languages
• State complexity of prefix distance of subregular languages
• State complexity of prefix distance
• State complexity of prefix distance

Cites work

• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 2201366 (Why is no real title available?)
• A Second Course in Formal Languages and Automata Theory
• A survey on operational state complexity
• Additive distances and quasi-distances between words
• Computing the edit distance of a regular language
• Descriptional and computational complexity of finite automata -- a survey
• Descriptional complexity of error detection
• Distances between languages and reflexivity of relations
• Efficient algorithms for computing the inner edit distance of a regular language via transducers
• Encyclopedia of Distances
• Parameterized Prefix Distance between Regular Languages
• Recent trends in descriptional complexity of formal languages
• State complexity of neighbourhoods and approximate pattern matching
• State complexity of prefix distance
• State complexity of prefix distance of subregular languages
• String distances and intrusion detection: Bridging the gap between formal languages and computer security
• The edit-distance between a regular language and a context-free language

Cited in

(12)

• Quasi-distances and weighted finite automata
• Quasi-distances and weighted finite automata
• Descriptional complexity of error detection
• State complexity of prefix distance of subregular languages
• State complexity of additive weighted finite automata
• State complexity of prefix distance of subregular languages
• State complexity of neighbourhoods and approximate pattern matching
• State complexity of prefix distance
• Regularity of a dynamic neighborhood of a regular language
• State complexity of prefix distance
• State complexity of suffix distance
• State complexity of neighbourhoods and approximate pattern matching

This page was built for publication: State complexity of suffix distance

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