Finite Approximations and Similarity of Languages

DOI10.1142/S0129054122500113zbMath1517.68215OpenAlexW4282002207WikidataQ114073260 ScholiaQ114073260MaRDI QIDQ6169950

Branislav Rovan, Andras Varga

Publication date: 15 August 2023

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

Full work available at URL: https://doi.org/10.1142/s0129054122500113

zbMATH Keywords

distance between languagesfinite approximation of languagesgrammars with energy

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Cites Work

• Unnamed Item
• Unnamed Item
• Approximate matching between a context-free grammar and a finite-state automaton
• Efficient algorithms for computing the inner edit distance of a regular language via transducers
• Relative prefix distance between languages
• Prefix Distance Between Regular Languages
• Parameterized Prefix Distance between Regular Languages
• State Complexity of Prefix Distance
• Edit-Distance Between Visibly Pushdown Languages
• Edit distance for timed automata
• The Cost of Traveling between Languages
• Computing the Edit-Distance between a Regular Language and a Context-Free Language
• Edit Distance for Pushdown Automata
• An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules
• Approximate Matching between a Context-Free Grammar and a Finite-State Automaton
• Top-Down Tree Edit-Distance of Regular Tree Languages
• Input-driven pushdown automata for edit distance neighborhood
• Alignment distance of regular tree languages
• Edit distance neighbourhoods of input-driven pushdown automata

This page was built for publication: Finite Approximations and Similarity of Languages