Meno:  Michal


Priezvisko:  Malý


Názov:  Complexity of Revised Stable Models


Vedúci:  Prof. Luís Moniz Pereira


Rok:  2007


Blok:  UI


Kµúčové slová:  logic programming, semantics, Stable Models, reductio ad absurdum, complexity, lattice


Abstrakt:  The theme of the work is to analyze the complexity of Revised Stable Models. Revised Stable models are a new semantics in logical programming, which brings a possibility of the socalled reductio ad absurdum reasoning, which was not possible in the stable models semantics.
At the beginning, there are presented the preliminaries and a motivation for the semantics, its definition and an intuitive explanation and visualization. Next come the analyze of the complexity and a free algebraic followup which describes the complexity of computing intersection of iteration of a monotonic operator in the lattice.
An alternative view of the semantics is drawn, which offers a possibility to introduce the reductio ad absurdum into stable models by using a transformation of the program.
The work concludes with an outline of possible future research themes.

