Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
From MaRDI portal
Publication:4507355
DOI10.1137/S0097539798345944zbMath0963.68077MaRDI QIDQ4507355
Giora Slutzki, Clifford Bergman
Publication date: 18 October 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
computational complexityvarietyclonenondeterminismlogarithmic spacepolynomial spacequasi-varietyterm-equivalencehyperexponential time
Analysis of algorithms and problem complexity (68Q25) Lattices of varieties (08B15) Abstract data types; algebraic specification (68Q65) Operations and polynomials in algebraic structures, primal algebras (08A40) Quasivarieties (08C15)
Related Items (19)
COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA ⋮ Complexity of the identity checking problem for finite semigroups. ⋮ COMPLEXITY OF SEMIGROUP IDENTITY CHECKING ⋮ The computational complexity of deciding whether a finite algebra generates a minimal variety ⋮ COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS ⋮ Semigroups embeddable in hyperplane face monoids. ⋮ Flat algebras and the translation of universal Horn logic to equational logic ⋮ Structure identification of Boolean relations and plain bases for co-clones ⋮ A minimal nonfinitely based semigroup whose variety is polynomially recognizable. ⋮ Checking quasi-identities in a finite semigroup may be computationally hard. ⋮ The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis ⋮ A note on the expressibility problem for modal logics and star-free regular expressions ⋮ EQUATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM ⋮ Computational complexity of some problems involving congruences on algebras ⋮ Deciding active structural completeness ⋮ The complexity of homomorphism factorization ⋮ On the complexity of the clone membership problem ⋮ INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS ⋮ COLLAPSING WORDS: A PROGRESS REPORT
This page was built for publication: Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
