THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE

DOI10.1142/S0129054113400315zbMath1293.68187MaRDI QIDQ5495420

Sang-Ki Ko, Kai Salomaa, Yo-Sub Han

Publication date: 4 August 2014

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

zbMATH Keywords

context-free languagesregular languagesedit-distanceLevenshtein distance

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (15)

Computing the Shortest String and the Edit-Distance for Parsing Expression Languages ⋮ State Complexity of Neighbourhoods and Approximate Pattern Matching ⋮ Decidability of involution hypercodes ⋮ Weak inverse neighborhoods of languages ⋮ Absent Subsequences in Words ⋮ State Complexity of Neighbourhoods and Approximate Pattern Matching ⋮ Edit-Distance Between Visibly Pushdown Languages ⋮ Consensus String Problem for Multiple Regular Languages ⋮ Descriptional Complexity of Error Detection ⋮ State Complexity of Suffix Distance ⋮ Consensus string problem for multiple regular languages ⋮ Input-driven pushdown automata for edit distance neighborhood ⋮ Quasi-Distances and Weighted Finite Automata ⋮ Prefix Distance Between Regular Languages ⋮ Approximate matching between a context-free grammar and a finite-state automaton

Cites Work

• Büchi context-free languages
• Distances between languages and reflexivity of relations
• How hard is computing the edit distance?
• Computing the edit distance of a regular language
• Order- n correction for regular languages
• The String-to-String Correction Problem
• Programming Techniques: Regular expression search algorithm
• EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS

This page was built for publication: THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE