Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
DOI10.1137/S0097539798345944zbMATH Open0963.68077MaRDI QIDQ4507355FDOQ4507355
Authors: Clifford Bergman, Giora Slutzki 
Publication date: 18 October 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
computational complexitylogarithmic spacenondeterminismvarietypolynomial spaceclonequasi-varietyterm-equivalencehyperexponential time
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)
Cited In (32)
- Testing for a semilattice term
- On the complexity functions for T-ideals of associative algebras
- G-Varieties of complexity 1
- A note on the expressibility problem for modal logics and star-free regular expressions
- COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
- Semigroups embeddable in hyperplane face monoids.
- 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.
- EQUATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM
- Complexity of the identity checking problem for finite semigroups.
- Title not available (Why is that?)
- 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
- The computational complexity of deciding whether a finite algebra generates a minimal variety
- Title not available (Why is that?)
- COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS
- A minimal nonfinitely based semigroup whose variety is polynomially recognizable.
- Flat algebras and the translation of universal Horn logic to equational logic
- Computational complexity of some problems involving congruences on algebras
- Polynomial-time tests for difference terms in idempotent varieties
- The complexity of problems connected with two-element algebras
- 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
- COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA
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)
