Baselice, Sabrina
(2008)
On program grounding in ASP.
[Tesi di dottorato]
(Unpublished)
| Item Type: |
Tesi di dottorato
|
| Lingua: |
English |
| Title: |
On program grounding in ASP |
| Creators: |
| Creators | Email |
|---|
| Baselice, Sabrina | UNSPECIFIED |
|
| Date: |
2008 |
| Date Type: |
Publication |
| Number of Pages: |
125 |
| Institution: |
Università degli Studi di Napoli Federico II |
| Department: |
Matematica e applicazioni "Renato Caccioppoli" |
| Dottorato: |
Scienze computazionali e informatiche |
| Ciclo di dottorato: |
20 |
| Coordinatore del Corso di dottorato: |
| nome | email |
|---|
| De Luca, Aldo | UNSPECIFIED |
|
| Tutor: |
| nome | email |
|---|
| Bonatti, Piero Andrea | UNSPECIFIED |
|
| Date: |
2008 |
| Number of Pages: |
125 |
| Uncontrolled Keywords: |
Knowledge representation and reasoning |
| Settori scientifico-disciplinari del MIUR: |
Area 01 - Scienze matematiche e informatiche > INF/01 - Informatica |
[error in script]
[error in script]
| Date Deposited: |
29 Jul 2008 |
| Last Modified: |
30 Apr 2014 19:28 |
| URI: |
http://www.fedoa.unina.it/id/eprint/1992 |
| DOI: |
10.6092/UNINA/FEDOA/1992 |
Abstract
Answer set programming (ASP) is a declarative problem solving framework introduced by Michael Gelfond and Vladimir Lifschitz in the late ’80s. ASP has received much
attention by researchers for its expressiveness and simpleness so that well-engineered and optimized implementations have been developed for it. However, state-of-the-art answer set solvers have still a strong limitation: they are not be able to reason on nonground programs and then the input program have to be instantiated before the solver can start to reason on it. Consequently,
answer set solvers (i) cannot handle infinite domains and (ii) use huge amounts of memory even if domains are finite. This work wants to give some contribution for these two not trivial problems.
First, I analyze finitary programs as a class of programs that can effectively deal with function symbols and recursion (hence infinite domains and models). Interestingly, even if finitary programs are computationally complete, their restrictions make it possible to keep complexity under control. I study the consequences of relaxing the restrictions on finitary programs and my results enforce a kind of minimality of the properties that characterize finitary programs.
Next, I investigate what happens when we “compose” two programs P and Q belonging to some particular classes that imposing them some restrictions guarantee good computational
properties, so obtaining a program P [ Q that, as a whole, might not be subject to the restrictions of P or Q but that again enjoys good computational properties.
Finally, I study a new approach to tackle the problem (ii) of ASP. The idea is to integrate answer set generation and constraint solving to reduce the memory requirements for a class of multi-sorted logic programs with cardinality constraints: constrained programs. I prove some
theoretical results, introduce provably sound and complete algorithms, and report experimental results on my prototype system for evaluating constrained programs, showing that my approach can solve problem instances with significantly larger domains.
Downloads per month over past year
Actions (login required)
 |
View Item |
