The existence of a near-unanimity function is decidable

DOI10.1007/S00012-013-0259-7MaRDI QIDQ2449447zbMATH OpenOpenAlexFDO

Authors D. N. Zhuk

Publication date 8 May 2014

Published in Algebra Universalis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.1671

zbMATH Keywords

decidabilityessential predicatenear-unanimityrelational structure

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Relational systems, laws of composition (08A02)

Abstract: We prove that the following problem is decidable: given a finite set of relations, decide whether this set admits a near-unanimity function.

Recommendations

• On the (un)decidability of a near-unanimity term
• The existence of a near-unanimity term in a finite algebra is decidable
• A BOUND ON THE NUMBER OF UNARY POLYNOMIAL FUNCTIONS AND A DECIDABILITY RESULT FOR NEAR-RINGS
• Clones, order varieties, near unanimity functions and holes
• Finitely related algebras in congruence distributive varieties have near unanimity terms

Cites work

• A polynomial-time algorithm for near-unanimity graphs
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Closed systems of functions and predicates
• Constraints, consistency and closure
• Finitely related algebras in congruence distributive varieties have near unanimity terms
• Graph theory
• On the (un)decidability of a near-unanimity term
• Order varieties and monotone retractions of finite posets
• Polynomial interpolation and the Chinese remainder theorem for algebraic systems
• Structure of clones in the precomplete class of self-dual functions in three-valued logic
• The cardinality of the set of all clones containing a given minimal clone on three elements
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The existence of a near-unanimity term in a finite algebra is decidable

Cited in

(5)

• Deciding absorption in relational structures
• On the (un)decidability of a near-unanimity term
• Dualities and algebras with a near-unanimity term
• The existence of a near-unanimity term in a finite algebra is decidable
• Deciding the existence of quasiweak near unanimity terms in finite algebras

This page was built for publication: The existence of a near-unanimity function is decidable

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