No Efficient Disjunction or Conjunction of Switch-Lists

DOI10.3233/SAT-220002MaRDI QIDQ5080958zbMATH OpenOpenAlexFDO

Authors Stefan Mengel

Publication date 1 June 2022

Published in Journal on Satisfiability, Boolean Modeling and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.04788

zbMATH Keywords

knowledge compilationswitch-lists

Mathematics Subject Classification ID

Knowledge representation (68T30) Boolean functions (06E30)

Abstract: It is shown that disjunction of two switch-lists can blow up the representation size exponentially. Since switch-lists can be negated without any increase in size, this shows that conjunction of switch-lists also leads to an exponential blow-up in general.

Recommendations

• Properties of Switch-List Representations of Boolean Functions
• An algorithm for disjunctive programs
• Disjunctive Programming
• Disjunctive programming
• On the computational power of Boolean decision lists
• scientific article; zbMATH DE number 2086400
• Mathematical Foundations of Computer Science 2004
• Decision lists and related classes of Boolean functions
• No feasible monotone interpolation for simple combinatorial reasoning
• Decision lists and related Boolean functions

Cites work

• scientific article; zbMATH DE number 1946853 (Why is no real title available?)
• Computing the minimum DNF representation of Boolean functions defined by intervals
• Disjunctive closures for knowledge compilation
• Properties of Switch-List Representations of Boolean Functions
• Recognition of tractable DNFs representable by a constant number of intervals

Cited in

(1)

• A faster implementation of EQ and SE queries for switch-list representations

This page was built for publication: No Efficient Disjunction or Conjunction of Switch-Lists

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