State Complexity of Prefix Distance

DOI10.1007/978-3-319-22360-5_20zbMath1371.68160OpenAlexW1440639274MaRDI QIDQ2947426

Kai Salomaa, David Rappaport, Timothy Ng

Publication date: 23 September 2015

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-22360-5_20

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (3)

Finite Approximations and Similarity of Languages ⋮ Descriptional Complexity of Error Detection ⋮ State Complexity of Prefix Distance of Subregular 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
• Efficient algorithms for computing the inner edit distance of a regular language via transducers
• Computing the edit distance of a regular language
• Parameterized Prefix Distance between Regular Languages
• STATE COMPLEXITY OF ADDITIVE WEIGHTED FINITE AUTOMATA
• 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