State complexity of prefix distance

DOI10.1016/j.tcs.2016.05.018zbMath1371.68161OpenAlexW2397866482MaRDI QIDQ2357110

Timothy Ng, David Rappaport, Kai Salomaa

Publication date: 19 June 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.05.018

zbMATH Keywords

finite automataregular languagesstate complexityprefix distance

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

State Complexity of Suffix Distance ⋮ Consensus string problem for multiple regular languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptional and computational complexity of finite automata -- a survey
• Intersection and union of regular languages and state complexity
• Distances between languages and reflexivity of relations
• Computing the edit distance of a regular language
• Parameterized Prefix Distance between Regular Languages
• STATE COMPLEXITY OF ADDITIVE WEIGHTED FINITE AUTOMATA
• State Complexity of Neighbourhoods and Approximate Pattern Matching
• A Second Course in Formal Languages and Automata Theory
• Maximal Words in Sequence Comparisons Based on Subword Composition
• Quasi-Distances and Weighted Finite Automata
• Encyclopedia of Distances

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