On the Complexity of Dualization of Monotone Disjunctive Normal Forms
Journal of AlgorithmsPublished 1 November 1996
Michael L. Fredman, Leonid Khachiyan
Citations416
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that the duality of a pair of monotone disjunctive normal forms of sizencan be tested inno(logn)time.
Abstract
We show that the duality of a pair of monotone disjunctive normal forms of sizencan be tested inno(log n)time.
Keywords
Computer Science
Artificial IntelligenceA theory of diagnosis from first principles
2,897 Citations1987Raymond Reiter
The theory accommodates diagnostic reasoning in a wide variety of practical settings, including digital and analogue circuits, medicine, and database updates, and reveals close connections between diagnostic reasoning and nonmonotonic reasoning.
Information Processing LettersOn generating all maximal independent sets
768 Citations1988David S. Johnson, Mihalis Yannakakis +1 more
An algorithm is presented that generates all maximal independent sets of a graph in lexicographic order, with only polynomial delay between the output of two successive independent sets, unless P=NP.
Journal of the ACMHow to assign votes in a distributed system
563 Citations1985Héctor García-Molina, Daniel Barbará
In this paper, both of these strategies for achieving mutual exclusion of groups of nodes without communication are studied in detail and it is shown that they are not equivalent in general (although they are in some cases) and a number of other interesting properties are proved.
SIAM Journal on ComputingIdentifying the Minimal Transversals of a Hypergraph and Related Problems
427 Citations1995Thomas Eiter, Georg Gottlob
Two decision problems on hypergraphs, hypergraph saturation and recognition of the transversal hypergraph, are considered and their significance for several search problems in applied computer science is discussed.
Journal of Computer and System SciencesDesign by example: An application of Armstrong relations
154 Citations1986Heikki Mannila, Kari‐Jouko Räihä
This paper analyzes the use of Armstrong relations in database design with functional dependencies, and shows how they and the usual representation of dependencies can be used together.
Information and ComputationComplexity of Identification and Dualization of Positive Boolean Functions
147 Citations1995Jan C. Bioch, Takanori Ibaraki
It is shown that the existence of an incrementally polynomial algorithm for this problem is equivalent to the exist of the following algorithms, where ƒ and g are positive Boolean functions.
Discrete Applied MathematicsOn generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
124 Citations1999Vladimir Gurvich, Leonid Khachiyan
It is shown that for some classes of polynomial-time computable monotone Boolean functions it is NP-hard to test either of the conditions D′=D or C′=C, which provides evidence that for each of these classes neither conjunctive nor disjunctive irredundant normal forms can be generated in total (or incremental) quasi-polynomial time.
Discrete MathematicsOn 3-chromatic hypergraphs
106 Citations1978József Beck
It is proved that of F, the uniform hypergraph, then the chromatic number of F is equal to 2, and the general (not necessarily uniform) case too is also proved.
Oracles and queries that are sufficient for exact learning (extended abstract)
33 Citations1994Nader H. Bshouty, Richard Cleve +2 more
There is a randomized polynomial-time algorithm that learns any class that is learnable from membership queries with unlimited computational power.
Discrete MathematicsOn the frequency of the most frequently occurring variable in dual monotone DNFs
13 Citations1997Vladimir Gurvich, Leonid Khachiyan
It is easily seen that max { μ 1, v 1, …, μ n , v n } ⩾ 1/log(| F | + | G |) is tight up to a factor of 2.
Boolean theory of coteries
11 Citations2002Toshihide Ibaraki, Tsunehiko Kameda
The authors take advantage of Boolean decomposition theorems to investigate 'decomposition' (or 'composition') of coteries, and prove that any function representing a nondominated coterie can be composed from copies of the 3-majority function.