Rational equivalence relations

DOI10.1016/0304-3975(86)90132-5zbMath0619.68051OpenAlexW3102069426MaRDI QIDQ1089801

J. Howard Johnson

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

zbMATH Keywords

class membership decision problemscomplexity of canonical function computationcontainment hierarchyequivalence kernels of rational functionsequivalence kernels of subsequential functionsfinite transductionsrational equivalence relationsrecognizable equivalence relations

Mathematics Subject Classification ID

Artificial intelligence (68T99) Theory of computing (68Q99)

Related Items (12)

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

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

This page was built for publication: Rational equivalence relations