The computational complexity of deciding whether a finite algebra generates a minimal variety

DOI10.1007/978-3-319-74772-9_9zbMATH Open1459.08007OpenAlexW2790053642MaRDI QIDQ4586419FDOQ4586419

Authors: George F. McNulty 

Publication date: 13 September 2018

Published in: Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-74772-9_9

Recommendations

• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• Computing generating sets of minimal size in finite algebras
• On the complexity of deciding homomorphism-homogeneity for finite algebras
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• scientific article; zbMATH DE number 1507184
• Computing the structure of finite algebras
• A Complete Characterization of the Algebras of Minimal Bilinear Complexity
• On the complexity of counting components of algebraic varieties
• Publication:4893238
• scientific article; zbMATH DE number 3977205

zbMATH Keywords

NP-hardnessfinite algebra decision problemsminimal variety of algebras

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of computation (including implicit computational complexity) (03D15) Varieties (08B99)

Cites Work

• Alternation
• TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE
• A Characterization of Minimal Locally Finite Varieties
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• THE RESIDUAL BOUNDS OF FINITE ALGEBRAS
• THE RESIDUAL BOUND OF A FINITE ALGEBRA IS NOT COMPUTABLE
• Full duality among graph algebras and flat graph algebras
• ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
• Title not available (Why is that?)
• Minimal, locally-finite varieties that are not finitely axiomatizable
• COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS
• A 2EXPTIME complete varietal membership problem
• On Comparison of Finite Algebras
• Title not available (Why is that?)
• Computational complexity of some problems involving congruences on algebras
• Title not available (Why is that?)
• The First Order Theory of N-Colorable Graphs
• The decidability of the affine completeness generation problem.
• COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA
• Finite bases for flat graph algebras

Cited In (1)

• Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting)

This page was built for publication: The computational complexity of deciding whether a finite algebra generates a minimal variety

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4586419)