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)

Full work available at URL https://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1000&context=math_pubs

zbMATH Keywords

clonecomputational complexityhyperexponential timelogarithmic spacenondeterminismpolynomial spacequasi-varietyterm-equivalencevariety

Mathematics Subject Classification ID

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

Recommendations

• Complexity of some problems in universal algebra. Extended abstract
• 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

(35)

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

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)