Known and new classes of generalized Horn formulae with polynomial recognition and SAT testing

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

Result language
angličtina
Original language name
Known and new classes of generalized Horn formulae with polynomial recognition and SAT testing
Original language description
In this paper we study several classes of Boolean formulae which generalize Horn formulae while preserving one of their main properties, namely the fact that satisfiability is decidable in polynomial time. We compare the known classes with respect to inclusion and define a hierarchy of new classes, which properly contains some of the known classes.
Czech name
Známé a nové třídy zobecněných Hornovských formulí s rozpoznáváním a SATem v polynomiálním čase
Czech description
V tomto článku zkoumáme několik tříd Booleovských formulí, které zobecňují Hornovské formule a přitom mají také tu vlastnost, že je pro ně SAT testovatelný v polynomiálním čase. Známé třídy jsou porovnány vzhledem k inkluzi a dále je definována hierarchie nových tříd, která obsahuje některé ze známých tříd jako vlastní podmnožiny.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/GA201%2F04%2F1102" target="_blank" >GA201/04/1102: Constraint-based planning and scheduling</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)

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

Similar results(10)