Finite Approximations and Similarity of Languages

DOI10.1142/S0129054122500113MaRDI QIDQ6169950zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

distance between languagesfinite approximation of languagesgrammars with energy

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(12)

• On Rough Approximations of Languages under Infinite Index Indiscernibility Relations
• Regular language distance and entropy
• Computation of distances for regular and context-free probabilistic languages
• scientific article; zbMATH DE number 1123618 (Why is no real title available?)
• scientific article; zbMATH DE number 2182424 (Why is no real title available?)
• 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
• 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)