On the readability of monotone Boolean formulae

DOI10.1007/S10878-009-9283-0zbMATH Open1229.90090OpenAlexW2159727921MaRDI QIDQ652622FDOQ652622

Authors: Kazuhisa Makino, Imran Rauf, Khaled Elbassioni 

Publication date: 15 December 2011

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

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

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

zbMATH Keywords

read-once functionsreadabilitymonotone Boolean functionscomplexity of monotone Boolean functions

Mathematics Subject Classification ID

Boolean programming (90C09)

Cites Work

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

Cited In (5)

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

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)