Combinatorial characterization of read-once formulae
From MaRDI portal
Publication:685684
DOI10.1016/0012-365X(93)90372-ZzbMath0781.06012OpenAlexW2029376824WikidataQ127725709 ScholiaQ127725709MaRDI QIDQ685684
Ilan Newman, Nathan Linial, Avi Wigderson, Michael E. Saks, Mauricio Karchmer
Publication date: 24 October 1993
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0012-365x(93)90372-z
Related Items (24)
Efficient parallel recognition algorithms of cographs and distance hereditary graphs ⋮ A global parallel algorithm for the hypergraph transversal problem ⋮ The read once formula of a series-parallel network ⋮ Using relevance queries for identification of read-once functions ⋮ On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems ⋮ Unnamed Item ⋮ Competitive evaluation of threshold functions in the priced information model ⋮ On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions ⋮ Read-once polynomial identity testing ⋮ Acyclic, or totally tight, two-person game forms: characterization and main properties ⋮ Decomposing complete edge-chromatic graphs and hypergraphs. Revisited ⋮ Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees ⋮ On effectivity functions of game forms ⋮ Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case ⋮ Decision lists and related Boolean functions ⋮ Building above read-once polynomials: identity testing and hardness of representation ⋮ Sandwich problem for \(\varPi\)- and \(\varDelta\)-free multigraphs and its applications to positional games ⋮ Critical properties and complexity measures of read-once Boolean functions ⋮ A note on monotone complexity and the rank of matrices ⋮ Double Horn functions ⋮ Characterizing Arithmetic Read-Once Formulae ⋮ Functions that are read-once on a subset of their inputs ⋮ Read-Once Functions Revisited and the Readability Number of a Boolean Function ⋮ Theory revision with queries: Horn, read-once, and parity formulas
Cites Work
This page was built for publication: Combinatorial characterization of read-once formulae
