Minimum self-dual decompositions of positive dual-minor Boolean functions

DOI10.1016/S0166-218X(99)00096-7zbMath0944.68003OpenAlexW1969508865WikidataQ127646758 ScholiaQ127646758MaRDI QIDQ1961458

Kazuhisa Makino, Toshihide Ibaraki, Jan C. Bioch

Publication date: 2 March 2000

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00096-7

zbMATH Keywords

Boolean function

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Network design and communication in computer systems (68M10)

Related Items (5)

Dual-bounded generating problems: Weighted transversals of a hypergraph ⋮ The complexity of modular decomposition of Boolean functions ⋮ A stronger LP bound for formula size lower bounds via clique constraints ⋮ An inequality for polymatroid functions and its applications. ⋮ Counting and enumerating aggregate classifiers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dualization of regular Boolean functions
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• On generating all maximal independent sets
• Functions computed by monotone Boolean formulas with no repeated variables
• Critical hypergraphs for the weak chromatic number
• Éléments ipsoduaux du treillis distributif libre et familles de Sperner ipsotransversales
• Decompositions of positive self-dual Boolean functions
• The fundamental theorem of voting schemes
• Complexity of identification and dualization of positive Boolean functions
• On the composition and decomposition of clutters
• On one criterion of the optihality of an algorithm for evaluating monotonic boolean functions
• A theory of the learnable
• How to assign votes in a distributed system
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• An Algorithm to Enumerate All Cutsets of a Graph in Linear Time per Cutset
• Learning read-once formulas with queries
• The solvability of positional games in pure strategies
• Time, clocks, and the ordering of events in a distributed system
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Optimal coteries for rings and related networks

This page was built for publication: Minimum self-dual decompositions of positive dual-minor Boolean functions