The Maximum Latency and Identification of Positive Boolean Functions

DOI10.1137/S0097539794276324zbMath0884.06012OpenAlexW2002660979MaRDI QIDQ4376178

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

dualizationtransversalpartial functionmaximum latencypositive Boolean functionidentification of Boolean functionsunknown vector

Mathematics Subject Classification ID

Related Items (19)

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

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