On the readability of monotone Boolean formulae

DOI10.1007/S10878-009-9283-0MaRDI QIDQ652622zbMATH OpenOpenAlexFDO

Authors Kazuhisa Makino, Imran Rauf, Khaled Elbassioni

Publication date 15 December 2011

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://doi.org/10.1007/s10878-009-9283-0

zbMATH Keywords

read-once functionsreadabilitymonotone Boolean functionscomplexity of monotone Boolean functions

Mathematics Subject Classification ID

Boolean programming (90C09)

Recommendations

• On the Readability of Monotone Boolean Formulae
• Read-Once Functions Revisited and the Readability Number of a Boolean Function
• Functions that are read-once on a subset of their inputs

Cites work

• scientific article; zbMATH DE number 5548206 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 3545568 (Why is no real title available?)
• scientific article; zbMATH DE number 219938 (Why is no real title available?)
• A characterization of span program size and improved lower bounds for monotone span programs
• Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
• Intersection Theorems for Systems of Sets
• Learning read-once formulas with queries
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
• The subchromatic number of a graph

Cited in

(5)

• Bipartite graphs of small readability
• Bipartite graphs of small readability
• Amplification of Bounded Depth Monotone Read-Once Boolean Formulae
• On the Readability of Monotone Boolean Formulae
• Read-Once Functions Revisited and the Readability Number of a Boolean Function

Describes a project that uses

Uses Software

• JBool

This page was built for publication: On the readability of monotone Boolean formulae

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