COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS

DOI10.1142/S0218196707004335zbMath1146.08002MaRDI 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 complexity; membership problem; finite algebra; finitely generated varieties

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

08A70: Applications of universal algebra in computer science

08B05: Equational logic, Mal'tsev conditions

Related Items

The computational complexity of deciding whether a finite algebra generates a minimal variety, Complexity of the identity checking problem for finite semigroups., 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