On bijunctive predicates over a finite set

DOI10.1515/DMA-2019-0006MaRDI QIDQ1741483zbMATH OpenOpenAlexWikidataFDO

Authors Svetlana N. Selezneva

Publication date 3 May 2019

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

Full work available at URL https://doi.org/10.1515/dma-2019-0006

zbMATH Keywords

bijunctive predicateconjunctive normal formconstraint satisfaction problemfunction over a finite setgeneralized satisfiability problemmajority functionpolynomial problempredicate over a finite set

Mathematics Subject Classification ID

Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On m-junctive predicates on a finite set
• On properties of multiaffine predicates on a finite set
• About finite predicate logic
• On weak positive predicates over a finite set
• Finite-degree predicates and two-variable first-order logic
• scientific article; zbMATH DE number 38461
• scientific article; zbMATH DE number 1406434
• Completeness of certain bimodal logics for subset spaces
• scientific article; zbMATH DE number 937394
• Finitely bi-conjugative relations

Cites work

• 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
• From local to global consistency
• scientific article; zbMATH DE number 3150816 (Why is no real title available?)
• The complexity of satisfiability problems
• Tractable constraints on ordered domains

Cited in

(8)

• scientific article; zbMATH DE number 4137897 (Why is no real title available?)
• scientific article; zbMATH DE number 4041859 (Why is no real title available?)
• On properties of functions representable in the form of a 2-CNF
• A generalisation of Schaefer's bijunctivity criterion
• On m-junctive predicates on a finite set
• scientific article; zbMATH DE number 7297896 (Why is no real title available?)
• On properties of multiaffine predicates on a finite set
• On weak positive predicates over a finite set

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

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