COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE

DOI10.1142/S0218196799000084MaRDI QIDQ3839875zbMATH OpenFDO

Authors Clifford Bergman, David W. Juedes, Giora Slutzki

Publication date 20 January 2000

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0218196799000084

zbMATH Keywords

alternating Turing machinecloneexponential timeterm-equivalencetree automata

Mathematics Subject Classification ID

Operations and polynomials in algebraic structures, primal algebras (08A40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1304317
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• scientific article; zbMATH DE number 3960994

Cites work

• Alternation
• Complete problems for deterministic polynomial time
• New problems complete for nondeterministic log space
• Oracle branching programs and Logspace versus \(P^*\)
• Relationships between nondeterministic and deterministic tape complexities

Cited in

(20)

• Computational complexity of terminological reasoning in BACK
• Testing for a semilattice term
• On the complexity of the Leibniz hierarchy
• Complexity of terms, composition, and hypersubstitution
• On the complexity of the clone membership problem
• The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis
• Computational complexity of various Mal'cev conditions
• Term equation satisfiability over finite algebras
• scientific article; zbMATH DE number 3848613 (Why is no real title available?)
• GENCLO AND TERMEQUIV ARE EXPTIME-COMPLETE
• ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• Complexity of term representations of finitary functions
• COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA
• scientific article; zbMATH DE number 1405451 (Why is no real title available?)
• Measuring the complexity of reductions between equivalence relations
• THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
• Idempotent n-permutable varieties.
• Computational complexity of some problems involving congruences on algebras
• A finite set of functions with an EXPTIME-complete composition problem

This page was built for publication: COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE

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