Structure identification of Boolean relations and plain bases for co-clones

DOI10.1016/J.JCSS.2008.02.005MaRDI QIDQ955340zbMATH OpenOpenAlexFDO

Authors Nadia Creignou, Bruno Zanuttini, Phokion G. Kolaitis

Publication date 19 November 2008

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2008.02.005

zbMATH Keywords

Boolean co-clonesBoolean constraintsclosure propertiescomputational complexityinverse satisfiability

Mathematics Subject Classification ID

Boolean functions (06E30) Applications of universal algebra in computer science (08A70) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Bases for Boolean co-clones
• Weak bases of Boolean co-clones
• On separation of Boolean clones by means of hyperidentities
• Characterization of clones of Boolean operations by identities
• scientific article; zbMATH DE number 7782790
• Boolean max-co-clones
• scientific article; zbMATH DE number 19597
• scientific article; zbMATH DE number 19687
• Boolean Structures
• scientific article; zbMATH DE number 18958

Cites work

• Bases for Boolean co-clones
• Closed systems of functions and predicates
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• scientific article; zbMATH DE number 3650557 (Why is no real title available?)
• scientific article; zbMATH DE number 3972929 (Why is no real title available?)
• scientific article; zbMATH DE number 1061261 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• On the Structure of Polynomial Time Reducibility
• Partial Polymorphisms and Constraint Satisfaction Problems
• Structure identification in relational data
• The complexity of satisfiability problems
• The Inverse Satisfiability Problem
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

Cited in

(25)

• Bases for Boolean co-clones
• Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
• Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
• Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
• Minimal distance of propositional models
• Dichotomy on intervals of strong partial Boolean clones
• What makes propositional abduction tractable
• The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
• Weak bases of Boolean co-clones
• The complexity of counting locally maximal satisfying assignments of Boolean CSPs
• Complexity Classifications for Logic-Based Argumentation
• The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
• Boolean max-co-clones
• Counting constraint satisfaction problems
• On the strength of uniqueness quantification in primitive positive formulas
• A dichotomy theorem for the inverse satisfiability problem
• Gap theorems for robust satisfiability: Boolean CSPs and beyond
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Partial Polymorphisms and Constraint Satisfaction Problems
• Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
• Parameterized complexity and kernelizability of max ones and exact ones problems
• Flow-augmentation. III: Complexity dichotomy for Boolean CSPS parameterized by the number of unsatisfied constraints
• Positive existential definability in finite structures
• An approximation trichotomy for Boolean \#CSP

This page was built for publication: Structure identification of Boolean relations and plain bases for co-clones

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