The Maximum Latency and Identification of Positive Boolean Functions

DOI10.1137/S0097539794276324MaRDI QIDQ4376178zbMATH OpenOpenAlexFDO

Authors Kazuhisa Makino, Toshihide Ibaraki

Publication date 10 February 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539794276324

zbMATH Keywords

transversaldualizationpartial functionmaximum latencypositive Boolean functionidentification of Boolean functionsunknown vector

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Boolean functions (06E30)

Recommendations

• A fast and simple algorithm for identifying 2-monotonic positive Boolean functions
• A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions
• ON EVALUATING BOOLEAN FUNCTIONS WITH UNRELIABLE TESTS
• Complexity of identification and dualization of positive Boolean functions
• Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle

Cited in

(21)

• Recognition and dualization of disguised bidual Horn functions.
• Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry
• Almost all monotone Boolean functions are polynomially learnable using membership queries
• On the complexity of monotone dualization and generating minimal hypergraph transversals
• Dual-bounded generating problems: Weighted transversals of a hypergraph
• Interior and exterior functions of positive Boolean functions.
• Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
• Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data
• Tree-shellability of Boolean functions
• Enumerating minimal dominating sets in chordal bipartite graphs
• Maximal sensitivity of Boolean nested canalizing functions
• On algorithms for construction of all irreducible partial covers
• On the fractional chromatic number of monotone self-dual Boolean functions
• On the fixed-parameter tractability of the equivalence test of monotone normal forms
• Computational aspects of monotone dualization: a brief survey
• Generating dual-bounded hypergraphs
• Unique key Horn functions
• A fast and simple algorithm for identifying 2-monotonic positive Boolean functions
• An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
• The Decomposition Tree for analyses of Boolean functions
• Complexity of identification and dualization of positive Boolean functions

This page was built for publication: The Maximum Latency and Identification of Positive Boolean Functions

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