On weak positive predicates over a finite set

DOI10.1515/DMA-2020-0019MaRDI QIDQ783121zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• On bijunctive predicates over a finite set
• On \(m\)-junctive predicates on a finite set
• scientific article; zbMATH DE number 4041859
• On the complexity of reducing weakly positive and weakly negative Boolean functions
• Tractable constraints in finite semilattices

Cites work

• scientific article; zbMATH DE number 3150816 (Why is no real title available?)
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Constraints, consistency and closure
• Existence theorems for weakly symmetric operations
• From local to global consistency
• On bijunctive predicates over a finite set
• The complexity of satisfiability problems
• The property of being polynomial for Mal’tsev constraint satisfaction problems
• Tractable constraints on ordered domains

Cited in

(4)

• On properties of multiaffine predicates on a finite set
• On \(m\)-junctive predicates on a finite set
• scientific article; zbMATH DE number 4137897 (Why is no real title available?)
• On bijunctive predicates over a finite set

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

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