On Hierarchies over the Class of SLUR Formulae

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

On Hierarchies over the Class of SLUR Formulae

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On Hierarchies over the Class of SLUR Formulae

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

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

Rok uplatnění

2011

Kód důvěrnosti údajů

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

Název statě ve sborníku

Proceedings of the 14th Czech-Japan Seminar on Data Analysis and Decision Making under Uncertainty

ISBN

978-80-7378-179-8

ISSN

—

e-ISSN

—

Počet stran výsledku

8

Strana od-do

1-8

Název nakladatele

Matfyzpress

Místo vydání

Praha

Místo konání akce

Hejnice, Czech Republic

Datum konání akce

18. 9. 2011

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—