logo

U bent hier

Waarschuwingsbericht

Opgelet! Dit event heeft al plaatsgehad.

Decidable Open Answer Set Programming

vrijdag, 10 februari, 2006 - 16:00
Campus: Brussels Humanities, Sciences & Engineering campus
Faculteit: Science and Bio-engineering Sciences
D
2.01
Stijn Heymans
doctoraatsverdediging

Traditionele paradigma's voor logisch programmeren hebben een gesloten wereld
veronderstelling: geldige deducties gebruiken enkel die constanten die in het
programma voorkomen. Het grounden van een logisch programma met zijn eigen
constanten verhindert het gebruik van logisch programmeren als conceptuele
modelleertaal. Een kennisingenieur zou alle ``invloedrijke" constanten moeten
voorzien.

Open answer set programmeren (OASP) lost dit gebrek aan modulariteit op door toe
te laten dat logische programma's geground worden met de elementen van een
willekeurige niet-lege aftelbare verzameling die de constanten in het programma
omvat. OASP is echter, in het algemeen, onbeslisbaar. Het onbeslisbare domino
probleem kan ernaar gereduceerd worden.

Ten einde beslisbaarheid te herwinnen, beperken we de vorm van logische
programma's. Dit levert 3 families van logische programma's op, gebaseerd op 3
verschillende reducties:

- Conceptuele Logische Programma's (CoLPs) zijn logische programma's met
unaire en binaire predikaten (mogelijk omgekeerde binaire predikaten)
waar regels een boomstructuur hebben. Beslisbaarheid van het nakijken
of er aan een predikaat voldaan kan worden, kan getoond worden door
een reductie naar het nakijken of er boomstructuren zijn die door een
\emph{two-way alternating tree automaton} aanvaard worden.

- Forest Logische Programma's (FoLPs) breiden CoLPs uit met constanten
en laten omgekeerde binaire predikaten weg. We identificeren
fragmenten die een reductie naar eindig answer set programmeren
toelaten (i.e., met een gesloten wereld veronderstelling).

- Guarded Programma's laten n-aire predikaten toe maar beperken het
gebruik van negatieve atomen, zoals bv. ongelijkheid. Beslisbaarheid
van guarded programma's hangt af van een vertaling naar guarded fixed
point logic, welke gezien kan worden als een uitbreiding van Clark's
completion met fixed point formules. We breiden guarded programma's
verder uit en tonen aan dat (alternation-free) guarded fixed point
logic equivalent is met het resulterende formalisme.

We bespreken de bovenstaande 3 families in detail. In het bijzonder illustreren
we hun expressiviteit door hen te relateren aan kennisrepresentatie formalismen
zoals description logics (DLs), mogelijk uitgebreid met DL-safe regels,
computation tree logic (CTL), Datalog LITE, (alternation-free) guarded fixed
point logic, en eindig answer set programmeren met omega-restricted programma's.
Bovendien integreren logische programma's onder de open answer set semantiek, in
1 unificerend formalisme, het beste van zowel het logisch programmeren paradigma
(nonmonotoniciteit door negation by failure) en het DL paradigma (beslisbaar
open domein redeneren). Dit maakt OASP een geschikte kandidaat voor Semantic
Web redeneren.