Properties of SLUR Formulae
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10126236" target="_blank" >RIV/00216208:11320/12:10126236 - isvavai.cz</a>
Result on the web
<a href="http://link.springer.com/chapter/10.1007%2F978-3-642-27660-6_15" target="_blank" >http://link.springer.com/chapter/10.1007%2F978-3-642-27660-6_15</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-27660-6_15" target="_blank" >10.1007/978-3-642-27660-6_15</a>
Alternative languages
Result language
angličtina
Original language name
Properties of SLUR Formulae
Original language description
Single look-ahead unit resolution (SLUR) algorithm is a non-deterministic 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. In this paper we show that the SLUR class is considerably larger than the above mentioned classes of CNFs by proving that every Boolean function has at least one CNF representation which belongs to the SLUR class. On the other hand, we show, that given a CNF it is coNP-complete to decide whether it belongs to the SLUR class or not. Finally, we define a non-collapsing hierarchy of CNF classes SLUR(i) in such a way that for every fixed i there is a polynomial time satisfiability
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GAP202%2F10%2F1188" target="_blank" >GAP202/10/1188: KnowSched: Knowledge Techniques in Scheduling</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Lecture Notes in Computer Science
ISSN
0302-9743
e-ISSN
—
Volume of the periodical
2012
Issue of the periodical within the volume
7147
Country of publishing house
DE - GERMANY
Number of pages
13
Pages from-to
177-189
UT code for WoS article
000307258500015
EID of the result in the Scopus database
—