State complexity of prefix distance of subregular languages

DOI10.1007/978-3-319-41114-9_15MaRDI QIDQ2829982zbMATH OpenOpenAlexFDO

Authors Timothy Ng, David Rappaport, Kai Salomaa

Publication date 9 November 2016

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01633944/file/416473_1_En_15_Chapter.pdf

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 2081044 (Why is no real title available?)
• A Second Course in Formal Languages and Automata Theory
• Additive distances and quasi-distances between words
• Descriptional and computational complexity of finite automata -- a survey
• Determination of finite automata accepting subregular languages
• Distances between languages and reflexivity of relations
• Encyclopedia of Distances
• Nondeterministic state complexity of star-free languages
• On NFAs where all states are final, initial, or both
• State complexity of prefix distance
• The magic number problem for subregular language families

Cited in

(8)

• Descriptional complexity of error detection
• State complexity of prefix distance of subregular languages
• Parameterized Prefix Distance between Regular Languages
• State complexity of suffix distance
• State complexity of neighbourhoods and approximate pattern matching
• State complexity of prefix distance
• State complexity of prefix distance
• State complexity of suffix distance

This page was built for publication: State complexity of prefix distance of subregular languages

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