Rational equivalence relations
Rational relations (finite transductions) which are equivalence relations are discussed. After establishing a containment hierarchy, the complexity of canonical function computation and a number of class membership decision problems are studied. The following classes are considered: (1) rational equivalence relations, (2) equivalence kernels of rational functions, (3) deterministic rational equivalence relations, (4) equivalence kernels of subsequential functions, (5) recognizable equivalence relations, (6) length-bounded rational equivalence relations, and (7) finite equivalence relations. Except for one open case ((1)\(=^{?}(2))\), Hasse diagrams are given to show the relative containments in the general and one-letter-alphabet cases. Canonical function application for an input of length n is shown to be \(O(n^ 2)\) time and space for (1), O(n) time and space for (2), (3), and (6), and O(n) time and constant space for the others. It is shown that transitivity, symmetry, reflexitivity, and membership in any of (1) through (5) are undecidable properties for rational relations whereas membership in (6) or (7) is decidable.
- A faster algorithm computing string edit distances
- A remark on finite transducers
- Efficient recognition of rational relations
- scientific article; zbMATH DE number 3911744 (Why is no real title available?)
- scientific article; zbMATH DE number 3660804 (Why is no real title available?)
- scientific article; zbMATH DE number 3784303 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3497806 (Why is no real title available?)
- scientific article; zbMATH DE number 3293666 (Why is no real title available?)
- scientific article; zbMATH DE number 3297798 (Why is no real title available?)
- Multitape one-way nonwriting automata
- On Relations Defined by Generalized Finite Automata
- Single-valued a-transducers
- Sur certains sous-monoïdes libres
- The equivalence problem for deterministic two-tape automata
- Transductions des langages de Chomsky
- Une caractérisation des fonctions séquentielles et des fonctions sous- séquentielles en tant que rélations rationnelles
- Small overlap monoids. II: Automatic structures and normal forms.
- Some decisional problems on rational relations
- Modelization of deterministic rational relations
- Distances between languages and reflexivity of relations
- Canonical equivalence relations on \(\mathbb Q^n\)
- The synthesis of Petri nets from path-automatic specifications
- Lexicographic decomposition of \(k\)-valued transducers
- On the representation of finite deterministic 2-tape automata
- Partitioning a symmetric rational relation into two asymmetric rational relations
- Rational equivalence of cusps
- The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata
- On finitely generated submonoids of virtually free groups
- Program equivalence checking by two-tape automata
- Regular path queries under approximate semantics
- Rational selecting relations and selectors
- Formal descriptions of code properties: decidability, complexity, implementation
- Equivalence Relations, Invariants, and Normal Forms
- Multi-sequential word relations
- scientific article; zbMATH DE number 3911744 (Why is no real title available?)
- scientific article; zbMATH DE number 3982545 (Why is no real title available?)
- scientific article; zbMATH DE number 4058890 (Why is no real title available?)
- A class of rational relations generalising the subword order
- Multi-sequential word relations
- scientific article; zbMATH DE number 1361478 (Why is no real title available?)
- scientific article; zbMATH DE number 2107585 (Why is no real title available?)
- A combinatorial study of k-valued rational relations
- Maximal r.e. equivalence relations
- Zero-Avoiding Transducers, Length Separable Relations, and the Rational Asymmetric Partition Problem
- Identities and transductions
- Synchronized rational relations of finite and infinite words
- A class of rational trace relations closed under composition
This page was built for publication: Rational equivalence relations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1089801)
