An improvement on the complexity of factoring read-once Boolean functions

DOI10.1016/J.DAM.2008.02.011MaRDI QIDQ944714zbMATH OpenOpenAlexFDO

Authors Martin Charles Golumbic, Aviad Mintz, Udi Rotics

Publication date 10 September 2008

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2008.02.011

zbMATH Keywords

cographslogicread-once functions

Mathematics Subject Classification ID

Boolean functions (06E30) Analysis of algorithms and problem complexity (68Q25) Boolean functions (94D10)

Recommendations

• Read-Once Functions Revisited and the Readability Number of a Boolean Function
• Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
• scientific article; zbMATH DE number 176867

Cites work

• A Linear Recognition Algorithm for Cographs
• A simple linear time algorithm for cograph recognition
• A simple linear time LexBFS cograph recognition algorithm.
• Complement reducible graphs
• Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
• Factoring Boolean functions using graph partitioning
• scientific article; zbMATH DE number 3859178 (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?)
• Learning read-once formulas with queries
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions

Cited in

(8)

• The complexity of AND-decomposition of Boolean functions
• Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
• On the Expressive Power of Read-Once Determinants
• scientific article; zbMATH DE number 4133979 (Why is no real title available?)
• Read-Once Functions Revisited and the Readability Number of a Boolean Function
• scientific article; zbMATH DE number 176867 (Why is no real title available?)
• scientific article; zbMATH DE number 7310075 (Why is no real title available?)
• On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems

This page was built for publication: An improvement on the complexity of factoring read-once Boolean functions

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