No Efficient Disjunction or Conjunction of Switch-Lists

DOI10.3233/SAT-220002zbMATH Open1495.68221arXiv2203.04788OpenAlexW4224882663MaRDI QIDQ5080958FDOQ5080958

Authors: Stefan Mengel 

Publication date: 1 June 2022

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

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.

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

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

zbMATH Keywords

knowledge compilationswitch-lists

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Disjunctive closures for knowledge compilation
• Computing the minimum DNF representation of Boolean functions defined by intervals
• Recognition of tractable DNFs representable by a constant number of intervals
• Properties of Switch-List Representations of Boolean Functions

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)