Complexity of identification and dualization of positive Boolean functions

DOI10.1006/inco.1995.1157zbMath1096.68633OpenAlexW2065895258MaRDI QIDQ2508337

Jan C. Bioch, Toshihide Ibaraki

Publication date: 10 October 2006

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: http://repub.eur.nl/pub/55247

Mathematics Subject Classification ID

Computational learning theory (68Q32) Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30)

Related Items

Sequential testing of complex systems: a review ⋮ Pareto-optimal patterns in logical analysis of data ⋮ Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data ⋮ Decompositions of positive self-dual Boolean functions ⋮ On the fixed-parameter tractability of the equivalence test of monotone normal forms ⋮ Logical analysis of data -- the vision of Peter L. Hammer ⋮ The complexity of modular decomposition of Boolean functions ⋮ An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation ⋮ Logical analysis of numerical data ⋮ Interior and exterior functions of Boolean functions ⋮ Error-free and best-fit extensions of partially defined Boolean functions ⋮ On Dualization over Distributive Lattices ⋮ The Minimal Hitting Set Generation Problem: Algorithms and Computation ⋮ Exact learning of subclasses of CDNF formulas with membership queries ⋮ Interior and exterior functions of positive Boolean functions. ⋮ An inequality for polymatroid functions and its applications. ⋮ Discovering all associations in discrete data using frequent minimally infrequent attribute sets ⋮ Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions ⋮ Bidual Horn functions and extensions ⋮ Minimum self-dual decompositions of positive dual-minor Boolean functions ⋮ On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions ⋮ Inner-core and outer-core functions of partially defined Boolean functions ⋮ A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs ⋮ Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic ⋮ Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions ⋮ Computational aspects of monotone dualization: a brief survey ⋮ On the complexity of monotone dualization and generating minimal hypergraph transversals ⋮ Self-duality of bounded monotone Boolean functions and related problems ⋮ On fuzzy relational equations and the covering problem ⋮ 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 ⋮ Translating between the representations of a ranked convex geometry ⋮ Translation among CNFs, characteristic models and ordered binary decision diagrams ⋮ On the fractional chromatic number of monotone self-dual Boolean functions ⋮ Dualization in lattices given by implicational bases ⋮ Efficiently enumerating hitting sets of hypergraphs arising in data profiling ⋮ Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices ⋮ The complexity of dependency detection and discovery in relational databases ⋮ Resolution based algorithms for the transversal hypergraph generation problem ⋮ Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs ⋮ On the relation between fuzzy max-Archimedean t-norm relational equations and the covering problem ⋮ Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices ⋮ Recognition and dualization of disguised bidual Horn functions. ⋮ Monotone Boolean dualization is in co-NP\([\log^{2}n\).] ⋮ Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms ⋮ Almost all monotone Boolean functions are polynomially learnable using membership queries