Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras

DOI10.1137/S0097539798345944MaRDI QIDQ4507355zbMATH OpenFDO

Authors Clifford Bergman, Giora Slutzki

Publication date 18 October 2000

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

computational complexitylogarithmic spacenondeterminismvarietypolynomial spaceclonequasi-varietyterm-equivalencehyperexponential time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract data types; algebraic specification (68Q65) Operations and polynomials in algebraic structures, primal algebras (08A40) Lattices of varieties (08B15) Quasivarieties (08C15)

Recommendations

• scientific article; zbMATH DE number 1304317
• The complexity of problems connected with two-element algebras
• scientific article; zbMATH DE number 3872682
• COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
• Computers and universal algebra: Some directions

Cited in

(32)

• COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA
• Testing for a semilattice term
• On the complexity functions for T-ideals of associative algebras
• A note on the expressibility problem for modal logics and star-free regular expressions
• G-Varieties of complexity 1
• Semigroups embeddable in hyperplane face monoids.
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• Constructive universal algebra: An introduction
• Structure identification of Boolean relations and plain bases for co-clones
• Checking quasi-identities in a finite semigroup may be computationally hard.
• Complexity of the identity checking problem for finite semigroups.
• EQUATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM
• scientific article; zbMATH DE number 1936750 (Why is no real title available?)
• The probability of triviality
• The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• Complexity of the normalization of algebras
• On the complexity of the clone membership problem
• COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
• Deciding active structural completeness
• A minimal nonfinitely based semigroup whose variety is polynomially recognizable.
• The computational complexity of deciding whether a finite algebra generates a minimal variety
• scientific article; zbMATH DE number 4154512 (Why is no real title available?)
• COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS
• Flat algebras and the translation of universal Horn logic to equational logic
• Computational complexity of some problems involving congruences on algebras
• The complexity of problems connected with two-element algebras
• Polynomial-time tests for difference terms in idempotent varieties
• Intersection of term equality sets in finitely defined algebras
• Unifiability and admissibility in finite algebras
• COLLAPSING WORDS: A PROGRESS REPORT
• The complexity of homomorphism factorization

This page was built for publication: Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras

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