COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS

DOI10.1142/S0218196707004335zbMath1146.08002OpenAlexW2094925573MaRDI QIDQ3502845

Marcin Kozik

Publication date: 20 May 2008

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

Full work available at URL: https://doi.org/10.1142/s0218196707004335

zbMATH Keywords

computational complexitymembership problemfinite algebrafinitely generated varieties

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Equational logic, Mal'tsev conditions (08B05)

Related Items (3)

Complexity of the identity checking problem for finite semigroups. ⋮ The computational complexity of deciding whether a finite algebra generates a minimal variety ⋮ A minimal nonfinitely based semigroup whose variety is polynomially recognizable.

Cites Work

• Unnamed Item
• Identities satisfied by a finite ring
• Relationships between nondeterministic and deterministic tape complexities
• Identical relations in finite groups
• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• Equational Bases for Lattice Theories.
• 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

This page was built for publication: COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS