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 reflexivity; subword distances

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Descriptional Complexity of Error Detection, State Complexity of Suffix Distance, Quasi-Distances and Weighted Finite Automata, THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE, Consensus String Problem for Multiple Regular Languages, Closest substring problems for regular languages, Edit distance neighbourhoods of input-driven pushdown automata, Approximate matching between a context-free grammar and a finite-state automaton, Bounded repairability of word languages, Decidability of involution hypercodes, Consensus string problem for multiple regular languages, State complexity of prefix distance, State Complexity of Prefix Distance of Subregular Languages, Prefix Distance Between Regular Languages, Duplications and Pseudo-Duplications, State Complexity of Prefix Distance, Edit-Distance Between Visibly Pushdown Languages, String distances and intrusion detection: Bridging the gap between formal languages and computer security

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item