Rational equivalence relations
From MaRDI portal
Publication:1089801
DOI10.1016/0304-3975(86)90132-5zbMath0619.68051OpenAlexW3102069426MaRDI QIDQ1089801
Publication date: 1986
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(86)90132-5
class membership decision problemscomplexity of canonical function computationcontainment hierarchyequivalence kernels of rational functionsequivalence kernels of subsequential functionsfinite transductionsrational equivalence relationsrecognizable equivalence relations
Related Items
The synthesis of Petri nets from path-automatic specifications, FORMAL DESCRIPTIONS OF CODE PROPERTIES: DECIDABILITY, COMPLEXITY, IMPLEMENTATION, Some decisional problems on rational relations, Lexicographic decomposition of \(k\)-valued transducers, On the representation of finite deterministic 2-tape automata, Program equivalence checking by two-tape automata, Synchronized rational relations of finite and infinite words, The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata, Regular path queries under approximate semantics, Small overlap monoids. II: Automatic structures and normal forms., On finitely generated submonoids of virtually free groups, Distances between languages and reflexivity of relations
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The equivalence problem for deterministic two-tape automata
- A faster algorithm computing string edit distances
- Efficient recognition of rational relations
- Transductions des langages de Chomsky
- Single-valued a-transducers
- Une caractérisation des fonctions séquentielles et des fonctions sous- séquentielles en tant que rélations rationnelles
- Multitape one-way nonwriting automata
- On Relations Defined by Generalized Finite Automata
- Sur certains sous-monoïdes libres
- A remark on finite transducers
