Tesi di Dottorato
Permanent URI for this communityTesi di Dottorato
Browse
6 results
Search Results
Item Computational tasks in answer set programming: algorithms and implementation(2014-12-01) Dodaro, Carmine; Leone, Nicola; Ricca, FrancescoL’Answer Set Programming (ASP) è un paradigma di programmazione dichiarativa basato sulla semantica dei modelli stabili. L’idea alla base di ASP è di codificare un problema computazionale in un programma logico i cui modelli stabili, anche detti answer set, corrispondono alle soluzioni del problema. L’espressività di ASP ed il numero crescente delle sue applicazioni hanno reso lo sviluppo di nuovi sistemi ASP un tema di ricerca attuale ed importante. La realizzazione di un sistema ASP richiede di implementare soluzioni efficienti per vari task computazionali. Questa tesi si occupa delle problematiche relative alla valutazione di programmi proposizionali, ed in particolare affronta i task di model generation, answer set checking, optimum answer set search e cautious reasoning. La combinazione dei primi due task corrisponde alla computazione degli answer set. Infatti, il task di model generation consiste nel generare dei modelli del programma in input, mentre il task di answer set checking ha il compito di verificare che siano effettivamente modelli stabili. Il primo task è correlato alla risoluzione di formule SAT, ed è implementato -nelle soluzioni moderne- con un algoritmo di backtracking simile al Conflict-Driven Clause Learning (CDCL); il secondo è risolto applicando una riduzione al problema dell’insoddisfacibilità di una formula SAT. In presenza di costrutti di ottimizzazione l’obiettivo di un sistema ASP è l’optimum answer set search, che corrisponde a calcolare un answer set che minimizza il numero di violazioni dei cosiddetti weak constraint presenti nel programma. Il cautious reasoning è il task principale nelle applicazioni dataoriented di ASP, e corrisponde a calcolare un sottoinsieme degli atomi che appartengono a tutti gli answer set di un programma. Si noti che tutti questi task presentano una elevata complessità computazionale. I contributi di questa tesi sono riassunti di seguito: (I) è stato studiato il task di model generation ed è stata proposta per la sua risoluzione una combinazione di tecniche che sono state originariamente utilizzate per risolvere il problema SAT; (II) è stato proposto un nuovo algoritmo per l’answer set checking che minimizza l’overhead dovuto all’esecuzione di chiamate multiple ad un oracolo co-NP. Tale algoritmo si basa su una strategia di valutazione incrementale ed euristiche progettate specificamente per migliorare l’efficienza della risoluzione di tale problema; (III) è stata proposta una famiglia di algoritmi per il calcolo di answer set ottimi di programmi con weak constraint. Tali soluzioni sono state ottenute adattando algoritmi proposti per risolvere il problema MaxSAT; (IV) è stato introdotto un nuovo framework di algoritmi anytime per il cautious reasoning in ASP che estende le proposte esistenti ed include un nuovo algoritmo ispirato a tecniche per il calcolo di backbone di teorie proposizionali. Queste tecniche sono state implementate in wasp 2, un nuovo sistema ASP per programmi proposizionali. L’efficacia delle tecniche proposte e l’efficienza del nuovo sistema sono state valutate empiricamente su istanze utilizzate nella competizioni per sistemi ASP e messe a disposizione sul Web.Item Integrated development environment for answer set programming(2012-11-30) Reale, Kristian; Leone, Nicola; Ricca, FrancescoAnswer Set Programming (ASP) is a truly-declarative programming paradigm proposed in the area of non-monotonic reasoning and logic programming. The successful application of ASP in a number of advanced projects, has renewed the interest in ASP-based systems for developing real-world applications. Nonethe- less, to boost the adoption of ASP-based technologies in the scientific commu- nity and especially in industry, it is important to provide effective programming tools, supporting the activities of researchers and implementors, and simplifying user interactions with ASP solvers. In the last few years, several tools for ASP- program development have been proposed, including (more or less advanced) editors and debuggers. However, ASP still lacks an Integrated Development Environment (IDE) supporting the entire life-cycle of ASP development, from (assisted) programs editing to application deployment. In this thesis we present ASPIDE, a comprehensive IDE for ASP. It inte- grates a cutting-edge editing tool (featuring dynamic syntax highlighting, on- line syntax correction, auto-completion, code-templates, quick-fixes, refactoring, etc.) with a collection of user-friendly graphical tools for program composi- tion, debugging, profiling, database access, solver execution configuration and output-handling. A comprehensive feature-wise comparison with existing environments for developing logic programs is also reported in this thesis, which shows that ASPIDE is a step forward in the present state of the art of tools for ASP programs development.Item Parallel evaluation of ASP programs:techniques and implementation(2011-11-30) Sirianni, Marco; Ricca, Francesco; Leone, NicolaAnswer Set Programming (ASP) is a purely declarative programming paradigm based on nonmonotonic reasoning and logic programming. The idea of ASP is to represent a given computational problem by a logic program such that its answer sets correspond to solutions, and then, use an answer set solver to find such solutions. The ASP language is very expressive and allows the representation of high-complexity problems (i.e., every problem in the second level of the polynomial hierarchy); unfortunately, the expressive power of the language comes at the price of an elevated cost of answer set computation. Even if this fact has initially discouraged the development of ASP system, nowadays several implementations are available, and the interest for ASP is growing in the scientific community as well as in the field of industry. In the last few years, significant technological enhancements have been achie- ved in the design of computer architectures, with a move towards the adoption of multi-core microprocessors. As a consequence, Symmetric Multi-Processing (SMP) has become available even on non-dedicated machines. Indeed, at the time of writing, the majority of computer systems and even laptops are equipped with (at least one) dual-core processor. However, in the ASP context, the avail- able systems were not designed to exploit parallel hardware; thus significant improvements can be obtained by developing ASP evaluation techniques that allow the full exploitation of the computational resources offered by modern hardware architectures. The evaluation of ASP programs is traditionally carried out in two steps. In the first step an input program P undergoes the so-called instantiation process, which produces a program P0 semantically equivalent to P but not containing any variable; in turn, P0 is evaluated by using a backtracking search algorithm in the second step. The aim of this thesis is the design and the assessment of a number of par- allel techniques devised for both steps of the evaluation of ASP programs. In particular, a three-level parallel instantiation technique is presented for improv- ing the efficiency of the instantiation process which might become a bottleneck in common situations, especially when huge input data has to been dealt with. Moreover, a parallel multi-heuristics search algorithm and a parallel lookahead technique have been conceived for optimizing the second phase of the evaluation. The mentioned parallel techniques has been implemented in the state-of-the- art ASP system DLV. An extensive experimental analysis has been carried out in order to assess the performance of the implemented prototypes. Experimental results have confirmed the efficiency of the implementation and the effectiveness of those techniques.Item DLVDB An ASP System for Data Intensive ApplicationsRisorsa elettronica(2014-04-01) Panetta, Claudio; Leone, Nicola; Terracina, GiorgioLa rapida crescita di sistemi informatici derivanti dalle diverse applicazioni cui Internet si presta, ha rapidamente aumentato la quantit`a di dati e di informazioni disponibili per l’elaborazione. In particolare, l’affermarsi del commercio elettronico, il diffondersi di sistemi per l’e-government delle pubbliche amministrazioni, l’ormai avviato processo di digitalizzazioni degli archivi e dei documenti in essi contenuti, la disponibilit`a di database medici sempre pi`u completi e ricchi di informazioni e, pi`u in generale, il sempre maggiore utilizzo dei sistemi informatici per la gestione strutturata di grandi quantit`a di dati hanno evidenziato l’urgenza di sviluppare nuove tecnologie che consentano di elaborare automaticamente ed efficientemente la quantit`a di dati derivante da questi settori emergenti. Uno degli utilizzi principali dei sistemi di basi di dati (DBMS) consiste nella memorizzazione e nel recupero efficiente di grandi quantit`a di dati. L’elaborazione di tali informazioni, specialmente quella finalizzata all’estrazione di nuova conoscenza, `e ormai riconosciuta come una tematica di ricerca di fondamentale importanza sia nell’ambito delle basi di dati, sia nell’ambito della ricerca industriale, in quanto offre grandi opportunit`a di sviluppo. In tale scenario, applicazioni come “Data Mining”, “Data Werehousing” e “Online Analytical Processing (OLAP)” hanno ulteriormente evidenziato la necessit`a di sviluppare sistemi di basi di dati che supportino linguaggi maggiormente espressivi, in grado di consentire elaborazioni sempre pi`u raffinate delle informazioni contenute nei Database. Il complesso di tali esigenze ha portato alla definizione di diverse estensioni per i modelli di rappresentazione dei dati (Modelli Relazionali basati sul concetto degli Oggetti), nonch´e alla definizione di nuovi costrutti sintattici (ricorsione e costrutti OLAP), ed all’estenzione dei DBMS (DataBase Management Systems) con linguaggi di programmazione di alto livello, basati su UDF (User Defined Functions). Purtroppo, per`o anche i migliori sistemi di basi di dati attualmente in commercio non sono sufficientemente potenti e generali da poter essere efficacemente utilizzati per risolvere molte delle emergenti applicazioni. In generale, gli attuali DBMS non contengono i meccanismi di ragionamento necessari per estrarre conoscenza complessa dai dati disponibili. Tali meccanismi, dovrebbero essere in grado sia di gestire grandi quantit`a di informazioni, sia di realizzare sofisticati processi di inferenza sui dati per trarne nuove conclusioni. Le capacit`a di ragionamento necessarie a tale scopo possono essere fornite dai sistemi basati su linguaggi logici. La Programmazione Logica Disgiuntiva (DLP) `e un formalismo che consente di rappresentare, in maniera semplice e naturale, forme di ragionamento non monotono, planning, problemi diagnostici e, pi`u in generale, problemi di elevata complessit`a computazionale. In DLP, un programma `e una collezione di regole logiche in cui `e consentito l’uso della disgiunzione nella testa delle regole e la negazione nel corpo. Una delle possibili semantiche per tali programmi `e basata sulla nozione di modello stabile (answer set). Ad ogni programma viene associato un insieme di answer set, ognuno corrispondente ad una possibile visione del dominio modellato. i La DLP sotto tale semantica viene comunemente riferita con il termine di Answer Set Programming (ASP). Il recente sviluppo di efficienti sistemi basati sulla programmazione logica come DLV [80], Smodels [101], XSB [114], ASSAT [84, 86], Cmodels [62, 61], CLASP [56], etc., ha rinnovato l’interesse nei campi del ragionamento non-monotono e della programmazione logica dichiarativa per la risoluzione di molti problemi in differenti aree applicative. Conseguentemente, tali sistemi possono fornire le funzionalit`a di inferenza e ragionamento richieste dalle nuove aree di applicazione che interessano i sistemi di basi di dati. Tuttavia, i sistemi basati sulla programmazione logica presentano notevoli limitazioni nella gestione di grandi quantit`a di dati non essendo dotati dell’opportuna tecnologia per rendere efficiente la loro gestione poich´e eseguono le loro elaborazioni facendo uso di strutture dati gestite direttamente in memoria centrale. Inoltre, la maggior parte delle applicazioni di interesse comune coinvolge grandi moli di dati su cui applicare complessi algoritmi di inferenza logica difficilmente elaborabili sia dai sistemi di programmazione logica, sia dai tradizionali database. Queste considerazioni mettono in evidenza la necessit`a di tecniche efficienti ed efficaci che combinino le qualit`a dei sistemi di inferenza logica con quelle dei sistemi di gestione delle basi di dati. In letteratura, le proposte di soluzione a tale problema sono culminate nei Sistemi di Basi di Dati Deduttive (DDS) [25, 52, 23, 63], che combinano le due realt`a dei sistemi logici e dei DBMS. In pratica, i DDS sono il risultato di una serie di tentativi di adattare i sistemi logici, che hanno una visione del mondo basata su pochi dati, ad applicazioni su grandi moli di dati attraverso interazioni intelligenti con le basi di dati. In particolare, i DDS sono forme avanzate di DBMS i cui linguaggi di interrogazione, basati sulla logica, sono molto espressivi. I DDS non memorizzano solo le informazioni esplicite in un database relazionale, ma memorizzano anche regole che consentono inferenze deduttive sui dati memorizzati. L’uso congiunto di tecniche sviluppate nell’ambito delle basi di dati relazionali con quelle della programmazione logica dichiarativa, consente in linea di principio ai DDS di realizzare ragionamenti complessi su grandi quantit`a di dati. Tuttavia, nonostante le loro potenzialit`a lo sviluppo di sistemi DDS a livello industriale non ha ricevuto molta attenzione. Ci`o principalmente `e stato dovuto al fatto che `e estremamente complesso ottenere sistemi particolarmente efficienti ed efficaci; infatti, le attuali implementazioni di DDS sono basate su due approcci estremi: uno basato sul miglioramento dell’elaborazione dei dati da parte dei sistemi logici, l’altro basato sull’aggiunta di capacit`a di ragionamento ai DBMS (ad esempio tramite l’uso di SQL99, o di funzioni esterne). Entrambi tali approcci presentano limitazioni importanti. In particolare, i DDS basati sulla logica possono gestire una quantit`a limitata di dati, dal momento che, gli attuali sistemi logici eseguono i loro ragionamenti direttamente in memoria centrale; inoltre, essi forniscono interoperabilit`a limitate con DBMS esterni. Al contrario, i DDS basati sui database offrono funzionalit`a avanzate di gestione dei dati, ma scarse capacit`a di ragionamento (sia a causa della poca espressivit`a dei linguaggi di interrogazione, sia a causa di problemi di efficienza). Riassumendo, possiamo affermare che: • Gli attuali sistemi di basi di dati implementano moduli sufficientemente robusti e flessibili capaci di gestire grandi quantit`a di dati, ma non possiedono un linguaggio sufficientemente espressivo da consentire ragionamenti complessi su questi dati. • I sistemi basati sulla programmazione logica, possiedono elevate capacit`a di ragionamento e sono in grado di modellare e risolvere con facilit`a problemi di elevata complessit`a ma presentano notevoli limitazioni nella gestione di grandi quantit`a di dati poich´e eseguono le loro elaborazioni facendo uso di strutture dati gestite direttamente in memoria centrale. ii • I sistemi di basi di dati deduttive consentono di gestire i dati memorizzati su DBMS, ma, dal momento che, eseguono i loro ragionamenti direttamente in memoria centrale, possono gestire una quantit`a limitata di dati; Dalle precedenti osservazioni, si evidenzia la necessit`a di realizzare applicazioni che combinino il potere espressivo dei sistemi di programmazione logica con l’efficiente gestione dei dati tipica dei database. Il contributo di questa tesi si colloca nell’area della ricerca sulle basi di dati deduttive con l’obiettivo di colmare il divario esistente tra sistemi logici e DBMS. In questa tesi viene descritto un nuovo sistema, DLVDB, che ha la caratteristica di possedere le capacit`a di elaborazione dati desiderabili da un DDS ma di supportare anche le funzionalit`a di ragionamento pi`u avanzate dei sistemi basati sulla programmazione logica disgiuntiva. DLVDB `e stato progettato come estensione del sistema DLV e combina l’esperienza maturata nell’ambito del progetto DLV nell’ottimizzare programmi logici con le avanzate capacit`a di gestione dei dati implementate nei DBMS esistenti. Ci`o consente di applicare tale sistema in ambiti che necessitano sia di valutare programmi complessi, sia di lavorare su grandi quantit`a di dati. DLVDB `e in grado di fornire, cos`ı sostanziali miglioramenti sia nelle prestazioni relative alla valutazione dei programmi logici, sia nella facilit`a di gestione dei dati di input e di output possibilmente distribuiti su pi`u database. L’interazione con le basi di dati `e realizzata per mezzo di connessioni ODBC che consentono di gestire in modo piuttosto semplice dati distribuiti su vari database in rete. DLVDB consente di applicare diverse tecniche di ottimizzazione sviluppate sia nell’ambito dei sistemi logici, come ad esempio i magic set, sia nell’ambito della gestione delle basi di dati, come ad esempio tecniche di join ordering, inoltre sono stati integrati nel sistema i predicati per l’aggregazione di DLV (count, min, max, avg, sum) che avvicinano il linguaggio alle potenzialit`a di SQL, ma anche la possibilit`a di integrare nel programma logico, per natura dichiarativo, chiamate a funzioni esterne sviluppate con tecniche procedurali; ci`o rende possibile integrare aspetti dichiarativi ed aspetti procedurali di un problema in un’unica framework. Infine, per consentire la gestione di tipi di dati con strutture ricorsive (es. XML) si `e introdotta la possibilit`a di gestire liste di elementi, eventualmente innestate, nel programma logico. Inoltre in questa tesi viene presentata l’attivit`a di analisi di tipo sperimentale effettuata al fine di valutare le prestazioni di DLVDB, soprattutto in riferimento a velocit`a di esecuzione di query e quantit`a di dati gestibili. Questi test hanno dimostrato come il sistema apporta numerosi vantaggi rispetto ai sistemi esistenti, sia in termini di tempi di esecuzione delle query, sia in termini di quantit`a di dati che esso riesce a gestire contemporaneamente. In sintesi, i contributi di questo lavoro possono essere riassunti come segue: • Sviluppo di un sistema in grado di fondere il potere espressivo dei sistemi ASP con l’efficiente gestione dei dati offerta dagli attuali Database; • Sviluppo di una strategia di valutazione dei programmi logici in grado di minimizzare l’utilizzo della memoria centrale massimizzando l’utilizzo delle tecnologie implementate dai DBMS; • Estensione del linguaggio DLP mediante l’introduzione di chiamate a funzioni esterne e il supporto a tipi di dati con strutture ricorsive come le liste; • Realizzazione di un’analisi comparativa tra le prestazioni offerte da DLVDB e le prestazioni dei sistemi esistenti.Item Extending the ASP System DLVDB to Support Complex Terms and Procedural Sub-tasks(2014-03-31) De Francesco, Erika; Terracina, Giorgio; Leone, NicolaIn many scientific and business scenarios, large amounts of data are generated and stored at increasing speed in local or distributed databases. Scientific experiments generating petabytes of data are daily performed in many laboratories all around the world. A growing number of ecommerce and e-business applications store and manage huge databases about products, clients and transactions. This explosive growth of data has raised an urgent need for new techniques and tools to intelligently and automatically infer useful information and knowledge from available data. In this context, Disjunctive Logic Programming (DLP) under the answer set semantics, often referred to as Answer Set Programming (ASP), has gained lot of interest during the last few years, since it represents a powerful method for declarative Knowledge Representation and Reasoning (KRR) tasks, which are critical to perform effective data analysis. The success of this method is demonstrated by the wide number of real-word applications that include, among others, information integration, frauds detection, diagnostics and planning, also motivating the implementation of several systems supporting DLP. The DLP language is very expressive and allows for modeling complex problems. However, despite the high expressiveness of this language, current DLP systems do not cope well with real world scenarios. In particular, the main limitations of current DLP systems can be summarized in four main issues [62]: (i) they are not capable of handling data intensive applications, since they work in main memory only; (ii) they provide a limited interoperability with external DBMSs; (iii) they are not well suited for modelling inherently procedural problems; (iv) they cannot reason about recursive data structures such as XML/HTML documents. The DLVDB system [41] has been conceived to overcome the above-mentioned limitations, by increasing the cooperation between ASP systems and databases. DLVDB allows substantial improvements in both the evaluation of logic programs and the management of input and output data distributed on several databases. Moreover, DLVDB presents enhanced features to improve its efficiency and usability for an effective exploitation of DLP in real-world scenarios. These features include: • Full support to disjunctive datalog with unstratified negation, and aggregate functions. • An evaluation strategy devoted to carry out as much as possible of the reasoning tasks in mass memory, thus enabling complex reasonings in data intensive applications without degrading performances. • Primitives to integrate data from different databases, in order to easily specify which data are to be considered as input or as output for the program. i In its early implementation, DLVDB did not support external predicates, list terms, and function symbols, which are of fundamental importance to enhance knowledge representation and reasoning capabilities of a DLP language. In particular, function symbols and lists terms allow the aggregation of atomic data, the manipulation of complex data structures and the generation of new symbols, while external predicates allow the isolation of procedural code units for calling them within declarative logic programs. The main goal of this thesis is to extend the DLVDB system to let it support the above mentioned language constructs, in order to improve its knowledge modelling power. By providing support to external predicates, list terms, and functional symbols, DLVDB allows to directly reason about recursive data structures, such as lists, semi-structured documents, and so on. This is a very important feature, both for standard knowledge-based tasks and for emerging applications, such as those manipulating XML documents. The main results of this thesis can be summarized as follows: • The DLVDB system has been extended to provide full support to external predicates. Since DLVDB transforms logic programs into SQL statements to enable database-oriented processing, we implemented external predicates by calls to database stored functions. This feature significantly improves the processing capabilities of DLVDB when the program includes inherently procedural subtasks that would be inefficiently solved in a declarative way. • Another extension to DLVDB has been designed and implemented to support list terms. We handle list terms through a rewriting of the rules using suitable external predicates. In particular, programs containing list terms are automatically rewritten to contain only terms and external predicates. The possibility to use lists allows programs to efficiently reason about recursive data structures, a feature that is required by many real-world applications. • A third extension to the DLVDB system has been realized to support programs with functional symbols. Similarly to list terms, rules are rewritten by replacing each functional term definition with calls to external predicates. Support to functional terms represents an important added value to DLVDB, since they are a very convenient means for generating domains and objects, allowing a more natural representation of problems in such domains. • A rich library of database stored functions for lists manipulation has been realized to facilitate the use of list terms in DLVDB through the use of external functions. Each function has been implemented for the DBMSs used as working databases for DLVDB, namely SQLServer, PostgreSQL, MySQL and Oracle. • Finally, a wide set of experiments has been performed to evaluate our extensions to the DLVDB system. All three extensions significantly improve the expressiveness of the supported language. The experimental results show that such extensions also significantly reduce the execution times as compared to DLVDB programs that do not support them. This thesis is organized as follows. Chapter 2 discusses the Answer Set Programming (ASP) framework based on a DLP language extended with aggregates, external predicates, functional terms and list terms. The chapter first defines the syntax of this language and its associated semantics, i.e., the answer set semantics. Then, it illustrates the usage of ASP as a formalism for knowledge representation and reasoning. ii Chapter 3 describes the DLVDB system. The chapter starts by introducing objectives and the architecture of DLVDB. Then, it focuses on the auxiliary directives the user can specify to let DLVDB interact with external databases. Finally, the chapter describes the evaluation strategy of DLP rules and their translation into SQL statements. Chapter 4 analyzes and compares the most recent ASP systems that support unstratified negation and other advanced constructs like disjunction, and various forms of constraints. The ASP systems are compared on the basis of two main aspects: the expressiveness of the supported language (e.g., its ability to express views, recursive rules, etc.), and the efficiency to answer a query (i.e., the quantity of data to be analyzed for answering a query, and the intrinsic complexity of the query itself). Chapter 5 describes the extensions that have been implemented to support external predicates, list terms, and functional terms in DLVDB. The chapter starts by providing the basic notions of database stored functions, which are used in our approach to implement the external predicates in DLVDB. Then, the evaluation strategies used for supporting external predicates, lists, and functional terms are described in detail. Chapter 6 presents an experimental evaluation of our extensions to the DLVDB system. The chapter provides a set of test cases to evaluate the benefits, in terms of performance and expressiveness, deriving from the use of our extensions (support to external predicates, lists, and functional terms) in DLVDB. Finally, Chapter 7 concludes the thesis by summarizing the main results achieved and by outlining future work, while Appendix A includes the source code of the implemented library for lists manipulations.Item Normal Form Nested Programs(2014-03-31) Bria, Annamaria; Faber, Wolfgang; Leone, NicolaNella Programmazione Logica Disgiuntiva (PLD) le regole sono costituite da una testa e da un corpo. La testa è una disgiunzione di atomi, mentre il corpo una congiunzione di letterali. La PLD, sotto la semantica degli Answer Set è ampiamente riconosciuta come importante strumento per la rappresentazione della conoscenza e del ragionamento non monotono. Lifschitz, Tang e Turner hanno esteso la semantica degli Answer Set (solo nel caso proposizionale o ground) ad una classe di programmi logici dove la testa e il corpo delle regole contengono espressioni innestate. Per espressioni innestate si intendono congiunzioni, disgiunzioni e negazione innestati arbitrariamente. Questa nuova classe di programmi è chiamata Programmi Logici Innestati e generalizza la classe dei programmi logici disgiuntivi proposizionali. Inoltre, è stato dimostrato che i programmi logici innestati possono essere trasformati in programmi logici disgiuntivi. Questi risultati ci permettono di valutare i programmi logici innestati usando i sistemi esistenti che supportano la PLD, come DLV, GnT, oppure Cmodels3. Si noti che le trasformazioni che consentono di ottenere i programma PLD introducono nuovi simboli e pertanto il programma risultante non è equivalente al programma originario nel senso classico. Ad ogni modo esiste una corrispondenza biunivoca tra gli answer set del programma innestato con gli answer set del programma trasformato. Sfortunatamente queste trasformazioni funzionano solo per programmi proposizionali e dunque non si possono usare le variabili, uno dei punti di forza dei programmi logici disgiuntivi. Questa limitazione diminuisce drasticamente l'applicabilità dei programmi logici innestati soprattutto quando il ragionamento è fatto su un numero molto grande di fatti. Una generalizzazione di queste tecniche a programmi che contengono variabili, non è ovvia. Per i programmi PLD l'indipendenza dal dominio è assicurata imponendo ai programmi delle condizioni sintattiche. Una di queste condizioni è nota come safety e per le regole PLD significa che ogni variabile che compare nella regola deve comparire anche in almeno un letterale positivo del corpo. Motivati da queste considerazioni, in questo lavoro di tesi estendiamo i programmi logici disgiuntivi non-ground ad una classe di programmi nei quali la testa delle regole è una formula in forma normale disgiuntiva composta da atomi, mentre il corpo è una formula in forma normale congiuntiva composta da letterali. Questi programmi sono chiamati programmi Normal Form Nested (NFN) e diversamente dai programmi logici innestati definiti da Lifschitz, Tang e Turner possono contenere variabili. In questo lavoro di tesi abbiamo studiato la semantica e la proprietà di indipendenza dal dominio e una trasformazione polinomiale dai programmi NFN ai programmi PLD, che preserva la safety. I principali contributi della tesi possono essere riassunti come segue. 1. Abbiamo esteso la DLP introducendo la congiunzione nella testa delle regole e la disgiunzione nel corpo delle stesse, ottenendo una nuova classe di programmi: i programmi NFN. 2. Abbiamo studiato le proprietà dei programmi NFN mostrando i seguenti risultati. a. Definita la Safety per i programmi NFN abbiamo dimostrato che ogni programma safe è indipendente dal dominio b. Gli answer set per i programmi NFN coincidono con gli answer set definiti da Lifschitz et al. per i programmi NLP, sul segmento del linguaggio comune. c. Gli answer set per i programmi NFN coincidono con i modelli stabili di Herbrand definiti da Ferraris et al. per le formule che corrispondono ai programmi NFN. d. Gli answer set per i programmi NFN coincidono con gli answer set per i programmi PLD definiti da Gelfond e Lifschitz. e. La nostra definizione di Safety per i programmi NFN è più generale di quella definita da Lee et al. sui programmi NFN. 3. Abbiamo progettato un algoritmo che trasforma i programmi NFN in programmi PLD in modo efficiente e abbiamo dimostrato che esso soddisfa importanti proprietà. a. La trasformazione preserva la safety. b. La taglia del programma trasformato è polinomiale nella taglia del programma NFN. c. Esiste una corrispondenza biunivoca tra gli answer set del programma NFN e quelli del programma riscritto. d. Abbiamo realizzato un sistema, nfn2dlp, che implementa l'algoritmo di riscrittura e un sistema che calcola gli answer set di un programma NFN: nfnsolve. Entrambi i tool sono disponibili al sito http://www.mat.unical.it/software/nfn2dlp/.; Università della Calabria