Bases for Boolean co-clones

DOI10.1016/J.IPL.2005.06.003MaRDI QIDQ1044708zbMATH OpenOpenAlexFDO

Authors Elmar Böhler, S. Reith, Henning Schnoor, Heribert Vollmer

Publication date 18 December 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2005.06.003

zbMATH Keywords

Boolean constraintsclosure propertiescombinatorial problemscomputational complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics in computer science (68R05)

Recommendations

• Weak bases of Boolean co-clones
• Structure identification of Boolean relations and plain bases for co-clones
• Boolean max-co-clones
• STACS 2004
• scientific article; zbMATH DE number 4072877

Cites work

• Complexity classifications of Boolean constraint satisfaction problems
• scientific article; zbMATH DE number 1061261 (Why is no real title available?)
• scientific article; zbMATH DE number 3307508 (Why is no real title available?)
• The complexity of satisfiability problems
• The complexity of satisfiability problems: Refining Schaefer's theorem
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

Cited in

(27)

• The complexity of satisfiability problems: Refining Schaefer's theorem
• Lewis dichotomies in many-valued logics
• The complexity of problems for quantified constraints
• On the complexity of the clone membership problem
• Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
• The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis
• Minimal distance of propositional models
• What makes propositional abduction tractable
• Weak bases of Boolean co-clones
• As Close as It Gets
• Complexity Classifications for Logic-Based Argumentation
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
• scientific article; zbMATH DE number 6970794 (Why is no real title available?)
• Boolean max-co-clones
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Partial Polymorphisms and Constraint Satisfaction Problems
• The next whisky bar
• The algebraic structure of the densification and the sparsification tasks for CSPs
• Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework
• Functional completeness and primitive positive decomposition of relations on finite domains
• Trichotomies in the complexity of minimal inference
• Flow-augmentation. III: Complexity dichotomy for Boolean CSPS parameterized by the number of unsatisfied constraints
• On when the union of two algebraic sets is algebraic
• On Boolean primitive positive clones
• Structure identification of Boolean relations and plain bases for co-clones
• The expressive power of valued constraints: Hierarchies and collapses
• An approximation trichotomy for Boolean \#CSP

This page was built for publication: Bases for Boolean co-clones

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