COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE

DOI10.1142/S0218196799000084zbMath0931.68058MaRDI QIDQ3839875

David W. Juedes, Giora Slutzki, Clifford Bergman

Publication date: 20 January 2000

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

zbMATH Keywords

clonetree automataexponential timealternating Turing machineterm-equivalence

Mathematics Subject Classification ID

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

Related Items (11)

COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA ⋮ GENCLO AND TERMEQUIV ARE EXPTIME-COMPLETE ⋮ Testing for a semilattice term ⋮ On the complexity of the Leibniz hierarchy ⋮ A finite set of functions with an EXPTIME-complete composition problem ⋮ The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis ⋮ Complexity of term representations of finitary functions ⋮ ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS ⋮ On the complexity of the clone membership problem ⋮ Idempotent n -permutable varieties ⋮ COMPUTATIONAL COMPLEXITY OF VARIOUS MAL'CEV CONDITIONS

Cites Work

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

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