Tesi di Dottorato
Permanent URI for this communityTesi di Dottorato
Browse
4 results
Search Results
Item Answer Set Programming with Functions(2014-04-01) Cozza, Susanna; Leone, NicolaL’Answer Set Programming (ASP) [Gelfond and Lifschitz, 1988; 1991] `e un formalismo che si `e affermato, in questi ultimi anni, come potente strumento di programmazione dichiarativa per la rappresentazione della conoscenza e per il ragionamento non monotono. La semantica su cui `e basato (denominata semantica answer set) estende la semantica dei modelli stabili (usata per i programmi logici ‘normali’) all’ambito della Programmazione Logica Disgiuntiva (PLD), in cui oltre alla negazione non monotona `e consentito anche l’uso della disgiunzione nella testa delle regole. Nell’ambito dell’ASP, un determinato problema computazionale viene rappresentato tramite un programma PLD che pu`o avere zero o pi`u modelli alternativi chiamati answer sets, ognuno dei quali corrisponde ad una possibile visione del dominio modellato. I linguaggi ASP consentono di rappresentare, in maniera semplice e naturale [Eiter et al., 2000], varie forme di ragionamento non monotono, planning, problemi diagnostici e, pi`u in generale, problemi di elevata complessit`a computazionale [Baral and Gelfond, 1994; Lobo et al., 1992;Wolfinger, 1994; Minker, 1994; Lifschitz, 1996; Eiter et al., 1999; Baral, 2003]. Dopo i primi sistemi sperimentali sul calcolo dei modelli stabili [Bell et al., 1994; Subrahmanian et al., 1995], attualmente sono disponibili un buon numero di sistemi che supportano in maniera efficiente l’ASP [Gebser et al., 2007a; Leone et al., 2006; Janhunen et al., 2006; Lierler, 2005; Lin and Zhao, 2004; Simons et al., 2002; Anger et al., 2001; East and Truszczy´nski, 2001; Egly et al., 2000]. Tra questi, quelli di maggiore successo sono: DLV [Leone et al., 2006], GnT [Janhunen et al., 2006] (estensione PLD del pi`u conosciuto Smodels [Simons et al., 2002]), e pi`u di recente clasp [Gebser et al., 2007a]. Tutto ci`o, se da un lato ha consentito l’impiego dell’ASP in contesti reali, dall’altro ha messo in evidenza le limitazioni dei sistemi attualmente disponibili. Uno dei principali limiti `e dato dall’inadeguato supporto a termini complessi quali funzioni, liste, set ed in generale costrutti che consentano, in maniera diretta, il ragionamento su strutture dati ricorsive e domini infiniti. Infatti, anche se la semantica answer set `e stata definita per linguaggi del primo ordine ‘generali’ quindi con anche termini funzionali, i sistemi ASP esistenti, sono essenzialmente basati su linguaggi senza funzioni. L’esigenza di estendere la PLD con un adeguato supporto ai termini funzionali `e percepita fortemente dalla comunit`a scientifica ASP, come testimoniato dai numerosi contributi pubblicati recentemente su questo tema [Lin andWang, 2008; Simkus and Eiter, 2007; Baselice et al., 2007; Bonatti, 3 2004; Syrj¨anen, 2001]. Tuttavia, non `e stato ancora proposto un linguaggio sufficientemente soddisfacente dal punto di vista linguistico (che abbia espressivit`a elevata) ed anche adatto ad essere integrato nei sistemi ASP esistenti. Infatti, attualmente nessun sistema ASP consente un uso effettivo di termini funzionali. I simboli di funzione o sono del tutto banditi dal linguaggio oppure sono soggetti a forti vincoli sintattici che non ne consentono l’uso in ambito ricorsivo. Obiettivo di questo lavoro di tesi `e il superamento di tali limitazioni. Il contributo del lavoro `e sia teorico che pratico ed ha portato all’implementazione di un sistema ASP che supporta adeguatamente i termini complessi: funzioni ma anche liste ed insiemi. Il principale contributo teorico riguarda la definizione formale di una nuova classe di programmi PLD: i programmi finitamente ground (FG). Tale classe supporta in maniera completa i simboli di funzione (essi sono ammessi anche in caso di regole ricorsive) e gode di alcune rilevanti propriet`a computazionali. Viene infatti dimostrato che, per tutti i programmi appartenenti alla classe, la valutazione secondo un approccio bottom-up, consente il calcolo effettivo degli answer set e di conseguenza, sia le query ground che le query non ground sono decidibili, qualsiasi sia la forma di ragionamento scelto (coraggioso o scettico). Un ulteriore risultato riguarda l’espressivit`a di questa classe: viene dimostrato che, qualsiasi funzione calcolabile pu`o essere espressa tramite un programma FG. Chiaramente, questo implica che il problema di riconoscere se un programma appartiene o meno alla classe, risulta essere indecidibile (in particolare, semidecidibile). Poich´e per alcuni utenti/applicazioni `e necessario avere una garanzia ‘‘a priori’’ della terminazione del programma, si `e ritenuto utile identificare una sottoclasse dei programmi FG, per la quale anche il problema del riconoscimento sia decidibile. Alcune condizioni sintattiche sono quindi state individuate come caratterizzanti per la nuova classe: i programmi a dominio finito (FD). La classe dei programmi FG `e, per alcuni aspetti, complementare alla classe dei programmi finitari [Bonatti, 2004]. La prima segue un approccio bottom-up, mentre la seconda top-down. Le due classi risultano essere incomparabili, nel senso che esistono dei programmi che appartengono alla prima ma non alla seconda e viceversa. Al fine di rendere valutabili secondo l’approccio bottom-up i programmi finitari, ampliando cos`ı la classe dei programmi FG, si `e fatto ricorso alla tecnica dei Magic Sets. Tale tecnica, nata nell’ambito delle Basi di Dati Deduttive a scopo di ottimizzazione, consiste in un metodo di riscrittura che simula la valutazione top-down di una query, modificando il programma originale e ag4 giungendo nuove regole che limitano la computazione ai dati rilevanti ai fini della query. Un opportuno adeguamento dell’algoritmo di riscrittura Magic Sets `e stato definito per le query finitamente ricorsive (le query il cui programma ‘rilevante’ `e finitario ed `e positivo). Dato un programma P ed una query ground finitamente ricorsiva Q, i seguenti risultati sono stati dimostrati riguardo il programma riscritto RW(Q;P): la sua dimensione `e lineare rispetto alla dimensione dell’input; risulta essere del tutto equivalente a quello originario ai fini della risposta alla query e soprattutto, tale programma `e FG, quindi pu`o essere valutato bottom-up (contrariamente al programma originale). Oltre ai contributi teorici sinora descritti, questa tesi presenta anche i risultati di un’attivit`a pi`u pratica, di tipo implementativo e di sperimentazione. Tale attivit`a `e stata svolta utilizzando DLV come sistema ASP di riferimento ed ha avuto come obiettivo l’estensione del linguaggio con simboli di funzione e pi`u in generale termini complessi quali liste e set. Un primo passo in questa direzione `e stata la realizzazione del supporto a funzioni esterne (plug-in). L’utente del sistema pu`o definire dei propri particolari predicati esterni (identificati tramite il prefisso ‘#’), implementati come funzioni C++ ed utilizzabili all’interno di un programma DLV. Ad ogni predicato esterno #p di arit`a n deve essere associata almeno una funzione C++ p0, detta ‘oracolo’. Tale funzione, della cui definizione `e responsabile l’utente, deve restituire un valore booleano e deve avere esattamente n argomenti. Un atomo ground #p(a1; : : : ; an) sar`a vero se e solo se il valore restituito dalla funzione p0(a1; : : : ; an) `e vero. Gli argomenti di una funzione oracolo possono essere sia di input che di output: ad argomenti di input corrispondono termini costanti o a cui `e gi`a stato assegnato un valore (termini ‘bound’) nel relativo predicato esterno, ad argomenti di output corrispondono termini variabili non legati ad alcun valore (termini ‘unbound’). L’introduzione delle funzioni esterne nel sistema DLV ha come conseguenza la possibilit`a di introdurre nuove costanti simboliche nel programma logico (Value Invention) e quindi rendere eventualmente infinito l’universo di Herbrand. Di conseguenza, per i programmi con Value Invention, non `e pi`u garantita la terminazione. Sono state quindi individuate un insieme di condizioni sintattiche tali da garantire la propriet`a di ‘istanziazione finita’ e quindi la terminazione, per un programma logico con funzioni esterne. Un riconoscitore di programmi logici che rispettano tali condizioni `e stato inoltre implementato ed integrato in DLV. Sfruttando le possibilit`a offerte dai predicati esterni, `e stato realizzato il sup5 porto a termini complessi di tipo funzionale. In pratica, in presenza di termini funzionali, una regola DLV viene ‘riscritta’ in maniera tale da tradurre la presenza del simbolo di funzione, nell’invocazione di un opportuno predicato esterno; questo si occupa poi della costruzione del termine complesso o, viceversa, dell’estrazione degli argomenti da esso. Il risultato ottenuto `e che i programmi FG, descritti in precedenza, sono pienamente supportati dal sistema. Un riconoscitore sintattico per i programmi a dominio finito consente di individuare ‘‘a priori’’ quei programmi la cui terminazione non `e garantita. A discrezione dell’utente, `e possibile disabilitare tale riconoscitore e sfruttare in pieno l’espressivit`a dei programmi FG, rinunciando per`o alla garanzia di terminazione. Il linguaggio effettivamente supportato dal sistema, oltre ai termini funzionali, prevede anche altre due tipologie di termini complessi: liste e set. Realizzati sfruttando lo stesso framework usato per le funzioni, liste e set sono stati corredati da una ricca libreria di funzioni di manipolazione che rendono ll loro uso molto agevole. Grazie a tali estensioni, il linguaggio di DLV `e diventato sempre pi`u adatto alla codifica immediata e compatta di problemi di rappresentazione della conoscenza. In sintesi, i contributi principali di questo lavoro di tesi sono: – la definizione formale della classe dei programmi finitamente ground; cio`e una nuova classe di programmi logici disgiuntivi che consente l’uso dei simboli di funzione (eventualmente con ricorsione) e che gode di rilevanti propriet` a computazionali quali: l’elevata espressivit`a, la computabilit`a bottomup degli answer set e quindi la decidibilit`a del ragionamento, anche in caso di query non ground; – l’utilizzo della tecnica dei Magic Sets per la riscrittura di programmi finitari positivi che non risultano appartenere alla classe dei programmi finitamente ground, ma sui quali `e comunque possibile valutare bottom-up delle query ground, grazie ad un’opportuna trasformazione del programma stesso; – la realizzazione di un sistema il cui linguaggio, oltre a supportare pienamente la classe dei programmi finitamente ground, consente l’integrazione nel programma logico di sorgenti computazionali esterne e l’utilizzo agevole di termini complessi quali liste e set; – la comparazione del nostro lavoro, in particolar modo con i programmi finitari, ma anche con altri approcci proposti in letteratura per l’estensione dei sistemi ASP con simboli di funzioneItem 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 CalabriaItem Eccient evaluation of disjunctive logic programs(2014-03-31) Catalano, Gelsomina; Leone, Nicola; Perri, SimonaAgli inizi degli anni ‘80, Jack Minker propose di accrescere la potenza della programmazione logica consentendo l’utilizzo della disgiunzione nelle teste delle regole e specificando come l’assunzione di mondo chiuso potesse essere estesa al linguaggio risultante, chiamato Programmazione Logica Disgiuntiva (DLP) [Minker, 1982; 1994]. Pi`u tardi, Michael Gelfond e Vladimir Lifschitz fornirono una semantica per la DLP, detta Answer Set Semantics [Gelfond and Lifschitz, 1991], che ha ricevuto larghi consensi nella comunit`a scientifica ed `e ora generalmente adottata per la DLP (detta anche Answer Set Programming – ASP). In accordo a tale semantica un programma logico disgiuntivo pu`o avere pi`u modelli alternativi (ma anche nessuno) ognuno corrispondente a una possibile visione del mondo rappresentato dal programma. Il linguaggio per la rappresentazione della conoscenza DLP `e molto espressivo in un senso matematicamente preciso; la DLP pu`o rappresentare ogni problema nella classe di complessit`a §P 2 (NPNP ) [Eiter et al., 1997b]. Dunque, sotto assunzioni ampiamente accettate, la DLP risulta strettamente pi`u espressiva della programmazione logica normale (senza disgiunzione), la cui espressivit`a `e limitata alle propriet`a decidibili in NP. L’espressivit`a della Programmazione Logica Disgiuntiva, ha importanti implicazioni pratiche, poich`e esistono problemi che possono essere rappresentati tramite un programma logico disgiuntivo, ma che non `e possibile esprimere con programmi logici senza disgiunzione, considerata la loro complessit`a [Eiter et al., 1997b]. Inoltre, la disgiunzione consente di rappresentare in modo pi`u semplice e naturale problemi di classi di complessit`a pi`u bassa. La DLP, con la Answer Set Semantics, `e oggi ampiamente riconosciuta come uno strumento potente per la rappresentazione della conoscenza e il ragionamento di senso comune [Baral and Gelfond, 1994; Lobo et al., 1992; Wolfinger, 1994; Eiter et al., 1999; Gelfond and Lifschitz, 1991; Lifschitz, 1996; Minker, 1994; Baral, 2002]. L’elevata complessit`a della DLP ha scoraggiato per molti anni la realizzazione di sistemi che implementassero tutte le caratteristiche di tale linguaggio. Dopo alcuni anni di ricerca sia teorica che algoritmica, oggi esistono diversi sistemi che supportano la DLP o parte di essa. Oltre ai sistemi di programmazione logica (non disgiuntivi) Smodels [Simons et al., 2002] e ASSAT [Lin and Zhao, 2002], sono disponibili anche alcuni sistemi di programmazione logica (disgiuntiva): DLV [Leone et al., 2006], GnT [Janhunen et al., 2003], and cmodels-3 [Lierler, 2005]. 3 In questa tesi ci concentriamo sul sistema DLV, che `e riconosciuto essere lo stato dell’arte della Programmazione Logica Disgiuntiva. DLV `e ampiamente sfruttato in tutto il mondo sia a scopo di ricerca che didattico. Per esempio, `e stato impiegato al CERN, il Laboratorio Europeo di Fisica delle Particelle di Ginevra, per un’applicazione di Basi di Dati deduttive che coinvolge la manipolazione di conoscenza complessa su basi di dati di grandi dimensioni. La compagnia polacca Rodan Systems S.A. sfrutta DLV in uno strumento per scoprire le manipolazioni dei prezzi e l’uso non autorizzato di informazioni confidenziali. Noi crediamo che la forza di DLV – la sua espressivit`a e l’ implementazione solida – lo renda attrattivo per tali applicazioni complesse. Anche dal punto di vista dell’efficienza, esso `e competitivo con i pi`u avanzati sistemi in quest’area come confermano i recenti confronti e valutazione delle prestazioni [Leone et al., 2006; Dix et al., 2003; Arieli et al., 2004], e i risultati della Prima Competizione di Sistemi Answer Set Programming http://asparagus.cs. uni-potsdam.de/contest/, in cui DLV `e risultato vincitore per le categorie DLP e MGS Competition (detta anche categoria “Royal”). Lo sviluppo di DLV `e iniziato nel 1996 al Politecnico di Vienna, nell’ambito di un progetto finanziato dalla Austrian Science Funds (FWF); oggi, DLV `e oggetto di una cooperazione internazionale tra l’Universit`a della Calabria e il Politecnico di Vienna. Il presente lavoro di tesi `e incentrato sullo studio della Programmazione Logica Disgiuntiva e l’ottimizzazione del sistema DLV, che implementa la DLP. I nostri studi hanno evidenziato che negli ultimi anni, la disponibilit`a di sistemi DLP affidabili, ha indotto a sfruttare la DLP in diverse aree applicative, ma i sistemi attuali non sono sufficientemente efficienti per molte di queste applicazioni. Questo lavoro affronta questo aspetto, proponendosi di superare questa limitazione, migliorando l’efficienza dei sistemi DLP e del sistema DLV tramite il progetto e l’implementazione di nuove tecniche di ottimizzazione. I moduli della maggior parte dei sistemi DLP operano su un’istanziazione ground del programma in input, cio`e un programma che non contiene alcuna variabile, ma `e semanticamente equivalente all’input originale [Eiter et al., 1997c]. Ogni programma P in input, inizialmente sottoposto alla cosiddetta procedura di istanziazione (detta anche istanziatore) che calcola, a partire da P, un programma ground P0 semanticamente equivalente. Poich`e questa fase pu`o essere molto costosa, avere un buon istanziatore `e un aspetto cruciale dei sistemi DLP. La ragione `e dovuta al fatto che ogni atomo di ciascuna regola pu`o essere istanziato utiliz4 zando ogni costante dell’Universo di Herbrand del programma, con una evidente esplosione esponenziale. L’istanziatore dovrebbe essere in grado di produrre un programma ground P0 avente gli stessi answer set di P e tale che: (i) P0 sia calcolato efficientemente da P, e (ii) P0 sia il pi`u piccolo possibile, e quindi possa essere valutato pi`u efficientemente da un solver DLP. Alcune applicazioni della DLP in aree emergenti come la gestione della conoscenza e l’integrazione delle informazioni, in cui devono essere processate grandi quantit`a di dati, hanno reso evidente la necessit`a di migliorare significativamente gli istanziatori DLP. La nostra attenzione `e stata rivolta al modulo di instanziazione di DLV, investigando nuove possibili direzioni per aumentarne l’efficienza. In particolare, in questa tesi, presentiamo due proposte per migliorare la procedura di istanziazione: ² Una nuova tecnica di Backjumping per l’istanziatore di DLV e ² Nuove tecniche di Indicizzazione per l’istanziatore di DLV Di seguito descriviamo brevemente queste due linee di ricerca. Backjumping. Proponiamo di sfruttare tecniche di backjumping che riduce la taglia del programma ground generato e ottimizza il tempo di esecuzione necessario a produrlo. In particolare, data una regola r che deve essere resa ground, tale algoritmo sfrutta informazioni semantiche e strutturali su r, per calcolare efficientemente le istanze ground di r, evitando la generazione di regole “inutili”. Cio`e per ogni regola r si calcola solo un sottoinsieme rilevante delle sue istanze ground, preservandone la semantica. Implementiamo questo algoritmo in DLV e conduciamo un’attivit`a di sperimentazione su un’ampia collezione di problemi. I risultati sperimentali sono molto positivi: la nuova tecnica migliora sensibilmente l’efficienza del sistema DLV su molte classi di problemi. Indicizzazione. Proponiamo di adoperare tecniche di indicizzazione per migliorare le performance della procedura di istanziazione di DLV, cio`e tecniche per il progetto e l’implementazione di strutture dati che permettano di accedere pi`u efficientemente a grandi datasets. In particolare, adattiamo al nostro contesto, una tecnica classica di indicizzazione sul primo argomento e proponiamo una strategia 5 di indicizzazione “on demand” in base alla quale gli indici non sono predeterminati, ma piuttosto vengono calcolati su un argomento qualsiasi durante la valutazione (e solo se sfruttabili). In pi`u definiamo due euristiche che possono essere usate per stabilire l’argomento pi`u appropriato da indicizzare, quando esistono diverse possibilit`a. Inoltre, implementiamo le tecniche di indicizzazione proposte in DLV e confrontiamo sperimentalmente le nostre strategie su una collezione di problemi provenienti da diversi domini comprese anche istanze di problemi reali. Il quadro generale risultante dagli esperimenti `e molto positivo: - Tutte le tecniche proposte e testate permettono di ottenere notevoli miglioramenti per l’esecuzione dell’istanziazione. - Lo schema di indicizzazione on demand d`a risultati migliori rispetto al classico schema sul primo argomento in un numero maggiore di casi e le performance migliorano particolarmente quando viene utilizzata una buona euristica. In definitiva, i metodi proposti migliorano sensibilmente l’efficienza dell’ istanziatore di DLV, consentendo l’utilizzo del sistema anche in applicazioni dataintensive. Comunque, per verificare ulteriormente la potenza del nuovo istanziatore conduciamo una profonda analisi sperimentale per confrontarlo con gli altri due pi`u popolari istanziatori, Lparse [Niemel¨a and Simons, 1997; Syrj¨anen, 2002] e GrinGo [Gebser et al., 2007b]. L’analisi conferma che, il nuovo istanziatore ha performance migliori degli altri su tutti i problemi testati, mentre il vecchio mostra performance simili agli altri. I risultati presentati in questa tesi sono rilevanti anche per altri due aspetti: da una parte, l’istanziatore di DLV pu`o essere sfruttato proficuamente da altri sistemi che non hanno un istanziatore proprio, per esempio ASSAT [Lin and Zhao, 2002] e Cmodels [Lierler and Maratea, 2004; Babovich, since 2002]. Infatti, questi sistemi possono usare DLV per ottenere il programma ground (lanciando DLV con l’opzione “-instantiate”), e poi applicare le proprie procedure per la valutazione del programma ground; d’altra parte, tutti i metodi proposti sono abbastanza generali e quindi, possono essere facilmente adattati per essere integrati nella fase di calcolo di altri istanziatori. In realt`a la nostra tecnica di backjumping `e stata gi`a integrata in altri due istanziatori, GrinGo e FO+ [Wittocx et al., 2008], con buoni risultati. Le buone performance di GrinGo in alcuni degli esperimenti condotti, infatti, sono dovuti all’utilizzo della nostra tecnica. 6 I principali contributi della tesi possono essere riassunti come segue: 1. Studiamo la DLP, la sua complessit`a e il suo utilizzo per la rappresentazione della conoscenza e il ragionamento non monotono. 2. Progettiamo un nuovo metodo, basato su una tecnica di backjumping, che consente di ridurre sia la taglia dell’istanziazione dei programmi DLP che il tempo necessario per generarla. Implementiamo il metodo proposto in DLV e conduciamo un’attivit`a di sperimentazione. 3. Definiamo due nuove strategie di indicizzazione, per ottimizzare il tempo di istanziazione di DLV. Inoltre, implementiamo il metodo proposto nel sistema DLV ed effettuiamo un’analisi sperimentale. 4. Confrontiamo l’istanziatore di DLV con altri due istanziatori, Lparse e GrinGo e discutiamo i risultati.Item A DLP-Based System for Ontology Representation and Reasoning(2012-11-09) Gallucci, Lorenzo; Leone, Nicola; Talia, DomenicoIn the last few years, the need for knowledge-based technologies is emerging in several application areas. Industries are now looking for semantic instruments for knowledge-representation and reasoning. In this context, ontologies (i.e., abstract models of a complex domain) have been recognized to be a fundamental tool; and the World Wide Web Consortium (W3C) has recommended OWL [58] as a standard language for ontologies. Some semantic assumptions of OWL, like Open World Assumption and non- Unique Name Assumption, make sense for the Web, but they are unsuited for Enterprise ontologies, that are specifications of information of business enterprises, which often evolve from relational databases, where both CWA and UNA are adopted. The subject of this thesis is OntoDLV , a system based on Disjunctive Logic Programming (DLP) for the specification and reasoning on enterprise ontologies. OntoDLP, the language of the system, overcomes the above-mentioned limitations of OWL, it adopts both CWA and UNA avoiding ”semantic clash” to enterprise databases. OntoDLP extends DLP with all the main ontology constructs including classes, inheritance, relations and axioms. The language is strongly typed, and includes also complex type constructors, like lists and sets. Importantly, OntoDLV supports a powerful interoperability mechanism with OWL, allowing the user to retrieve information also from OWL Ontologies and to reason on top of that by exploiting OntoDLP powerful deduction rules. The system is endowed with a powerful Application Programming Interface and is already used in a number of real-world applications,including agent-based systems and information extraction applications.