Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Balázs Szörényi:

TR05-023 | 16th February 2005
Robert H. Sloan, Balázs Szörényi, György Turán

On k-term DNF with largest number of prime implicants

It is known that a k-term DNF can have at most 2^k ? 1 prime implicants and this bound is sharp. We determine all k-term DNF having the maximal number of prime implicants. It is shown that a DNF is maximal if and only if it corresponds to a non-repeating ... more >>>

TR03-039 | 19th May 2003
Judy Goldsmith, Robert H. Sloan, Balázs Szörényi, György Turán

Theory Revision with Queries: Horn, Read-once, and Parity Formulas

A theory, in this context, is a Boolean formula; it is
used to classify instances, or truth assignments. Theories
can model real-world phenomena, and can do so more or less
The theory revision, or concept revision, problem is to
correct a given, roughly correct concept.
This problem is ... more >>>

ISSN 1433-8092 | Imprint