EQUATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM

DOI10.1142/S0218196708004913zbMath1163.08002MaRDI QIDQ3601326

Ross Willard, Zoltán Székely, George F. McNulty

Publication date: 10 February 2009

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

zbMATH Keywords

graph algebravariety of algebrasautomatic algebraequational complexityinherently nonfinitely basedmembership problem of a varietyshift automorphism method

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Equational logic, Mal'tsev conditions (08B05) Model theory of finite structures (03C13) Equational classes, universal algebra in model theory (03C05)

Related Items (11)

Constraint satisfaction, irredundant axiomatisability and continuous colouring ⋮ On the equational complexity of RRA ⋮ Algebras from finite group actions and a question of Eilenberg and Schützenberger ⋮ Dualizability of automatic algebras. ⋮ General algebra and its applications 2013: problem session. ⋮ A juggler's dozen of easy\(^\dag\) problems (\(^\dag\) Well, easily formulated \dots). ⋮ EVERY SHIFT AUTOMORPHISM VARIETY HAS AN INFINITE SUBDIRECTLY IRREDUCIBLE MEMBER ⋮ THERE IS NO FINITE-VARIABLE EQUATIONAL AXIOMATIZATION OF REPRESENTABLE RELATION ALGEBRAS OVER WEAKLY REPRESENTABLE RELATION ALGEBRAS ⋮ The equational complexity of Lyndon's algebra ⋮ Low Growth Equational Complexity ⋮ Characteristic inference rules

Cites Work

• Unnamed Item
• Nonfinitely based pseudovarieties and inherently nonfinitely based varieties
• A modular inherently nonfinitely based lattice
• Lyndon's groupoid is not inherently nonfinitely based
• The Birkhoff theorem for finite algebras
• On pseudovarieties
• Inherently nonfinitely based lattices
• Finite algebras of finite complexity
• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• Inherently Nonfinitely Based Solvable Algebras
• Tarski’s finite basis problem via 𝐀(𝒯)
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• THE RESIDUAL BOUNDS OF FINITE ALGEBRAS
• THE RESIDUAL BOUND OF A FINITE ALGEBRA IS NOT COMPUTABLE
• TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE
• THE MEMBERSHIP PROBLEM IN FINITE FLAT HYPERGRAPH ALGEBRAS
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• Subdirect unions in universal algebra
• Finite bases for flat graph algebras

This page was built for publication: EQUATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM