Attributes | Values |
---|
rdf:type
| |
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 SLUR class 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.
- 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 SLUR class 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. (en)
|
Title
| - On Hierarchies over the Class of SLUR Formulae
- On Hierarchies over the Class of SLUR Formulae (en)
|
skos:prefLabel
| - On Hierarchies over the Class of SLUR Formulae
- On Hierarchies over the Class of SLUR Formulae (en)
|
skos:notation
| - RIV/00216208:11320/11:10103736!RIV12-MSM-11320___
|
http://linked.open...avai/riv/aktivita
| |
http://linked.open...avai/riv/aktivity
| |
http://linked.open...vai/riv/dodaniDat
| |
http://linked.open...aciTvurceVysledku
| |
http://linked.open.../riv/druhVysledku
| |
http://linked.open...iv/duvernostUdaju
| |
http://linked.open...titaPredkladatele
| |
http://linked.open...dnocenehoVysledku
| |
http://linked.open...ai/riv/idVysledku
| - RIV/00216208:11320/11:10103736
|
http://linked.open...riv/jazykVysledku
| |
http://linked.open.../riv/klicovaSlova
| - Formulae; SLUR; Class; Hierarchies (en)
|
http://linked.open.../riv/klicoveSlovo
| |
http://linked.open...ontrolniKodProRIV
| |
http://linked.open...v/mistoKonaniAkce
| |
http://linked.open...i/riv/mistoVydani
| |
http://linked.open...i/riv/nazevZdroje
| - Proceedings of the 14th Czech-Japan Seminar on Data Analysis and Decision Making under Uncertainty
|
http://linked.open...in/vavai/riv/obor
| |
http://linked.open...ichTvurcuVysledku
| |
http://linked.open...cetTvurcuVysledku
| |
http://linked.open...UplatneniVysledku
| |
http://linked.open...iv/tvurceVysledku
| - Kučera, Petr
- Vlček, Václav
- Balyo, Tomáš
- Gurský, Štefan
|
http://linked.open...vavai/riv/typAkce
| |
http://linked.open.../riv/zahajeniAkce
| |
http://linked.open...n/vavai/riv/zamer
| |
number of pages
| |
http://purl.org/ne...btex#hasPublisher
| |
https://schema.org/isbn
| |
http://localhost/t...ganizacniJednotka
| |