Distances between languages and reflexivity of relations

DOI10.1016/S0304-3975(01)00238-9zbMath1016.68045WikidataQ61677529 ScholiaQ61677529MaRDI QIDQ1608895

Giovanni Pighizzini, Christian Choffrut

Publication date: 13 August 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

almost reflexivitysubword distances

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (23)

A similarity measure for formal languages based on convergent geometric series ⋮ Duplications and Pseudo-Duplications ⋮ State Complexity of Prefix Distance ⋮ Bounded repairability of word languages ⋮ Loopless algorithms to generate maximum length Gray cycles wrt. \(k\)-character substitutions ⋮ Decidability of involution hypercodes ⋮ When variable-length codes meet the field of error detection ⋮ Weights of formal languages based on geometric series with an application to automatic grading ⋮ Topologies for error-detecting variable-length codes ⋮ Edit-Distance Between Visibly Pushdown Languages ⋮ Consensus String Problem for Multiple Regular Languages ⋮ Closest substring problems for regular languages ⋮ Descriptional Complexity of Error Detection ⋮ State Complexity of Suffix Distance ⋮ Consensus string problem for multiple regular languages ⋮ Edit distance neighbourhoods of input-driven pushdown automata ⋮ Quasi-Distances and Weighted Finite Automata ⋮ State Complexity of Prefix Distance of Subregular Languages ⋮ Prefix Distance Between Regular Languages ⋮ THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE ⋮ String distances and intrusion detection: Bridging the gap between formal languages and computer security ⋮ Approximate matching between a context-free grammar and a finite-state automaton ⋮ State complexity of prefix distance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Synchronized rational relations of finite and infinite words
• Improved limitedness theorems on finite automata with distance functions
• Limitedness theorem on finite automata with distance functions
• Rational equivalence relations
• Semigroups, Presburger formulas, and languages
• On Relations Defined by Generalized Finite Automata

This page was built for publication: Distances between languages and reflexivity of relations