On Hierarchies over the Class of SLUR Formulae

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10103736" target="_blank" >RIV/00216208:11320/11:10103736 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
On Hierarchies over the Class of SLUR Formulae
Original language description
Single look-ahead unit resolution (SLUR) algorithm is a nondeterministic polynomial time algorithm which for a given input formula in a conjunctive normal form (CNF) either outputs its satisfying assignment or gives up. A CNF formula belongs to the SLURclass if no sequence of nondeterministic choices causes the SLUR algorithm to give up on it. The SLUR class is reasonably large. It is known to properly contain the well studied classes of Horn CNFs, renamable Horn CNFs, extended Horn CNFs, and CC-balanced CNFs. Recently, it was shown, that a canonical representation of a Boolean function always belongs to the SLUR class. In this paper we extend this result by showing, that this remains true even for some representations, which are not far from the canonical one. We also generalize the hierarchy of classes of Boolean formulae which was built on top of the CLUR class in previous paper.
Czech name
—
Czech description
—

Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Publication year
2011
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of the 14th Czech-Japan Seminar on Data Analysis and Decision Making under Uncertainty
ISBN
978-80-7378-179-8
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
1-8
Publisher name
Matfyzpress
Place of publication
Praha
Event location
Hejnice, Czech Republic
Event date
Sep 18, 2011
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)