Finite Approximations and Similarity of Languages

DOI10.1142/S0129054122500113zbMATH Open1517.68215OpenAlexW4282002207WikidataQ114073260 ScholiaQ114073260MaRDI QIDQ6169950FDOQ6169950

Authors: 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

Recommendations

• Distances of formal languages
• Computation of distances for regular and context-free probabilistic languages
• Relative prefix distance between languages
• scientific article; zbMATH DE number 569758
• Distances between languages and reflexivity of relations

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

• Approximate matching between a context-free grammar and a finite-state automaton
• The Cost of Traveling between Languages
• Approximate matching between a context-free grammar and a finite-state automaton
• An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules
• Efficient algorithms for computing the inner edit distance of a regular language via transducers
• Prefix distance between regular languages
• Computing the edit-distance between a regular language and a context-free language
• Input-driven pushdown automata for edit distance neighborhood
• Edit-distance between visibly pushdown languages
• Parameterized Prefix Distance between Regular Languages
• Relative prefix distance between languages
• Edit distance for pushdown automata
• State complexity of prefix distance
• Alignment distance of regular tree languages
• Edit distance for timed automata
• Edit distance neighbourhoods of input-driven pushdown automata
• Distances of formal languages
• Title not available (Why is that?)
• Top-down tree edit-distance of regular tree languages

Cited In (12)

• Regular language distance and entropy
• Title not available (Why is that?)
• Computation of distances for regular and context-free probabilistic languages
• Title not available (Why is that?)
• Structural, Syntactic, and Statistical Pattern Recognition
• Similarity in languages and programs
• On Syntactic versus Computational Views of Approximability
• Some uncountable hierarchies of formal languages
• A Similarity Measure for Cyclic Unary Regular Languages
• Distances of formal languages
• On Rough Approximations of Languages under Infinite Index Indiscernibility Relations
• Approximately satisfied properties of systems and simple language homomorphisms

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

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