The Maximum Latency and Identification of Positive Boolean Functions
DOI10.1137/S0097539794276324zbMATH Open0884.06012OpenAlexW2002660979MaRDI QIDQ4376178FDOQ4376178
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
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
transversaldualizationpartial functionmaximum latencypositive Boolean functionidentification of Boolean functionsunknown vector
Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Boolean functions (06E30)
Cited In (21)
- 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.
- Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data
- Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
- 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
- Generating dual-bounded hypergraphs
- Computational aspects of monotone dualization: a brief survey
- Unique key Horn functions
- A fast and simple algorithm for identifying 2-monotonic positive Boolean functions
- The Decomposition Tree for analyses of Boolean functions
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- Complexity of identification and dualization of positive Boolean functions
- Recognition and dualization of disguised bidual Horn 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)
