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

computational complexitycombinatorial problemsclosure propertiesBoolean constraints

Mathematics Subject Classification ID

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

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

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

Cited in

(23)

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

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)