On weak positive predicates over a finite set

DOI10.1515/dma-2020-0019zbMath1445.68142OpenAlexW3035348643MaRDI QIDQ783121

Svetlana N. Selezneva

Publication date: 30 July 2020

Published in: Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/dma-2020-0019

zbMATH Keywords

constraint satisfaction problemconjunctive normal formgeneralized satisfiability problemfunction over finite setpolynomial-time problempredicate over finite setsemilattice functionweak positive predicate

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Logic in computer science (03B70) Computational aspects of satisfiability (68R07)

Related Items (2)

On properties of multiaffine predicates on a finite set ⋮ On m-Junctive Predicates on a Finite Set

Cites Work

• Unnamed Item
• Existence theorems for weakly symmetric operations
• From local to global consistency
• Constraints, consistency and closure
• On bijunctive predicates over a finite set
• The property of being polynomial for Mal’tsev constraint satisfaction problems
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Closure properties of constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• Tractable constraints on ordered domains

This page was built for publication: On weak positive predicates over a finite set