Varieties with few subalgebras of powers
From MaRDI portal
Publication:3550542
DOI10.1090/S0002-9947-09-04874-0zbMath1190.08004MaRDI QIDQ3550542
Ralph McKenzie, Ross Willard, Petar Marković, Paweł M. Idziak, Joel D. Berman, Matthew A. Valeriote
Publication date: 31 March 2010
Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1090/s0002-9947-09-04874-0
68Q25: Analysis of algorithms and problem complexity
08A70: Applications of universal algebra in computer science
08B05: Equational logic, Mal'tsev conditions
08A30: Subalgebras, congruence relations
Related Items
Unnamed Item, Unnamed Item, THE DISTRIBUTIVITY SPECTRUM OF BAKER’S VARIETY, Algebra and the Complexity of Digraph CSPs: a Survey, The matrix taxonomy of finitely complete categories, Congruence preserving expansions of nilpotent algebras, Unnamed Item, Growth rates of algebras, II: Wiegold dichotomy, Complexity and polymorphisms for digraph constraint problems under some basic constructions, Recent Results on the Algebraic Approach to the CSP, Unnamed Item, Between an n-ary and an n + 1-ary near-unanimity term, CLAP: A New Algorithm for Promise CSPs, Constraint satisfaction problem: what makes the problem easy, Finitely generated equational classes, Naturally dualizable algebras omitting types 1 and 5 have a cube term, Preserving near unanimity terms under products, A relational description of higher commutators in Mal'cev varieties, On the growth of generating sets for direct powers of semigroups., Finitely related clones and algebras with cube terms., An easy test for congruence modularity, Colouring, constraint satisfaction, and complexity, On the number of finite algebraic structures, Mal'tsev conditions, lack of absorption, and solvability., Maltsev families of varieties closed under join or Maltsev product, Quantified constraint satisfaction and the polynomially generated powers property, A strong Mal'cev condition for locally finite varieties omitting the unary type, On the expression complexity of equivalence and isomorphism of primitive positive formulas, On the complexity of \(\mathbb{H}\)-coloring for special oriented trees, Cube term blockers without finiteness, On singleton arc consistency for CSPs defined by monotone patterns, Taylor's modularity conjecture and related problems for idempotent varieties, Generic expression hardness results for primitive positive formula comparison, On finitely related semigroups., A compact representation for modular semilattices and its applications, Mal'tsev condition satisfaction problems for conditions which imply edge terms, Mitschke's theorem is sharp, Existence of cube terms in finite algebras, Algebras from congruences, Random models of idempotent linear Maltsev conditions. I. Idemprimality, The number of clones determined by disjunctions of unary relations, Testing for edge terms is decidable, Finite bands are finitely related, Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties., Dualizable algebras with parallelogram terms, THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA, Deciding absorption, COMPUTATIONAL COMPLEXITY OF VARIOUS MAL'CEV CONDITIONS, On finite Taylor algebras, COUNTING THE RELATIONS COMPATIBLE WITH AN ALGEBRA, GROWTH OF GENERATING SETS FOR DIRECT POWERS OF CLASSICAL ALGEBRAIC STRUCTURES, GROWTH RATES OF ALGEBRAS, I: POINTED CUBE TERMS, Constraint Satisfaction Problems Solvable by Local Consistency Methods, Independence of algebras with edge term, On Singleton Arc Consistency for CSPs Defined by Monotone Patterns, Quantified Constraint Satisfaction and the Polynomially Generated Powers Property
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The expressive rate of constraints
- Polynomial interpolation and the Chinese remainder theorem for algebraic systems
- On the algebraic structure of combinatorial problems
- Learnability of quantified formulas.
- Learning intersection-closed classes with signatures
- Few subpowers, congruence distributivity and near-unanimity terms
- Near-unanimity is decomposable
- Dualizable algebras with parallelogram terms
- Generative complexity in algebra
- The structure of locally finite varieties with polynomially many models
- Geometrical methods in congruence modular algebras
- The structure of finite algebras
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Vaught's Conjecture for Varieties
- Classifying the Complexity of Constraints Using Finite Algebras
- Tractability and Learnability Arising from Algebras with Few Subpowers
- A Simple Algorithm for Mal'tsev Constraints
- Categoricity in Power
- A Characterization of Modularity for Congruence Lattices of Algebras*