scientific article; zbMATH DE number 3982545

zbMATH Open0607.68061MaRDI QIDQ3746906FDOQ3746906

Authors J. Howard Johnson

Publication date 1986

zbMATH Keywords

rational functionsHasse diagramssubsequential functionsclass membership decision problemscomplexity of canonical function computationcontainment hierarchyfinite transductionsRational relations

Mathematics Subject Classification ID

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

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

(17)

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

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)