COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES

DOI10.1142/S0218196702001085zbMath1046.08006MaRDI QIDQ3043639

Zoltán Székely

Publication date: 6 August 2004

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

zbMATH Keywords

flat graph algebras

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Varieties (08B99)

Related Items (16)

THE MEMBERSHIP PROBLEM IN FINITE FLAT HYPERGRAPH ALGEBRAS ⋮ Complexity of the identity checking problem for finite semigroups. ⋮ Axiomatisability and hardness for universal Horn classes of hypergraphs ⋮ The computational complexity of deciding whether a finite algebra generates a minimal variety ⋮ COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS ⋮ On varieties of flat nil-semirings ⋮ Dualizability of automatic algebras. ⋮ Flat algebras and the translation of universal Horn logic to equational logic ⋮ A juggler's dozen of easy\(^\dag\) problems (\(^\dag\) Well, easily formulated \dots). ⋮ A finite set of functions with an EXPTIME-complete composition problem ⋮ A minimal nonfinitely based semigroup whose variety is polynomially recognizable. ⋮ The equational complexity of Lyndon's algebra ⋮ EQUATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM ⋮ 2004 Summer Meeting of the Association for Symbolic Logic ⋮ INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS ⋮ Nonfinitely based ai-semirings with finitely based semigroup reducts

Cites Work

• The complexity of equivalence for commutative rings
• Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra
• Finite equational bases for congruence modular varieties
• A four-element algebra whose identities are not finitely based
• A field guide to equational logic
• Finite equational bases for finite algebras in a congruence-distributive equational class
• Algorithmic problems for finite groups and finite \(0\)-simple semigroups
• Identities satisfied by a finite ring
• On McKenzie's method
• Identical relations in finite groups
• Isomorphism Testing of Unary Algebras
• Equational Bases for Lattice Theories.
• Polynomial Time Uniform Word Problems
• ALGORITHMIC PROBLEMS IN VARIETIES
• THE RESIDUAL BOUNDS OF FINITE ALGEBRAS
• TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE

This page was built for publication: COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES