scientific article; zbMATH DE number 3982545

MaRDI QIDQ3746906zbMATH OpenFDO

Authors J. Howard Johnson

Publication date 1986

zbMATH Keywords

class membership decision problemscomplexity of canonical function computationcontainment hierarchyfinite transductionsHasse diagramsrational functionsRational relationssubsequential functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Rational equivalence relations
• scientific article; zbMATH DE number 3911744
• Decision problems for subclasses of rational relations over finite and infinite words
• scientific article; zbMATH DE number 7058469
• Some decisional problems on rational relations

Cited in

(18)

• Rational equivalence relations
• Separating strings with small automata
• Canonical equivalence relations on \(\mathbb Q^n\)
• Finite transducers and rational transductions
• Partitioning a symmetric rational relation into two asymmetric rational relations
• Rational equivalence of cusps
• Rational selecting relations and selectors
• Equivalence Relations, Invariants, and Normal Forms
• scientific article; zbMATH DE number 3911744 (Why is no real title available?)
• scientific article; zbMATH DE number 1361478 (Why is no real title available?)
• scientific article; zbMATH DE number 2107585 (Why is no real title available?)
• Separating words with machines and groups
• A combinatorial study of k-valued rational relations
• Maximal r.e. equivalence relations
• Identities and transductions
• An explicit algorithm for normal forms in small overlap monoids
• Separating words problem over groups
• Complexity classes of equivalence problems revisited

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3746906)