Browsing by Author "Leone, Nicola"

Now showing 1 - 20 of 51

3d web-based parallel applications for the numerical modeling of natural phenomena
(2014-11-28) Parise, Roberto; Leone, Nicola; D'Ambrosio, Donato; Spataro, William
In this thesis, I designed and implemented three new web applications tai- lored for the Cellular Automata (CA) simulation models SCIDDICA-k1, SCIARA-fv3 and ABBAMPAU, making use of the GoogleWeb Toolkit frame- work and WebGL. Moreover, I have contributed to the optimizations of the numerical models mentioned above and I also developed part of a library, called OpenCAL, for developing CA simulation models in C/C++. In this case, my most signi - cant contribution regarded the support given to the parallelization through the OpenCL standard, in order to facilitate with a few lines of codes, the par- allelization for the execution on any device, especially on General Purpose Computation with Graphics Processing Units (GPGPU). The development of the web applications involved the implementation of strategies so that optimizing the server load in the connections' management and enhancing the real time visualization of maps on devices of any kind, even mobile. As regards the OpenCAL library, the tests performed on a test models has shown signi cant performance improvements in terms of speedup, thanks also to the use of some new optimization strategies. In this way, the validity of the use of graphics processing units as alternative to more expensive hardware solutions for the parallelization of CA models has been con rmed.
Advanced Techniques and Systems for Data and Process Management
(2014-03-31) Granata, Luigi; Greco, Gianluigi; Leone, Nicola
Il lavoro di tesi viene suddiviso in due parti che trattano rispettivamente di tecniche avanzate e sistemi per la gestione dei dati e per il mining dei processi. Sono state affrontate problematiche relative all’efficienza della risposta alle interrogazioni su una base di dati, l’integrazioni di pi`u sorgenti di dati, e la progettazione di un sistema per il mining di processi. In particolare, i principali contributi della tesi sono: (1) Un nuovo modo di calcolare alberi di decomposizione di una interrogazione i cui query plan garantiscano un tempo di esecuzione al pi`u di complessit`a polinomiale. (2) Lo studio di tecniche emetodologie innovative, basate su logica computazionale, per i sistemi per l’integrazione di sorgenti informative e lo sviluppo di un prototipo che le implementi. (3) Lo studio di tecniche ed algoritmi per il mining di processi e lo sviluppo di una suite che le implementi. (1) Tecniche di risposta alle interrogazioni su basi di dati Rispondere ad interrogazioni su una basa di dati pu`o essere un processomolto costoso da un punto di vista computazionale. Per far fronte a questa problematica, in letteratura sono stati proposti vari approcci. Alcuni di essi sono basati su moduli per l’ottimizzazione delle interrogazioni che sfruttino le informazioni quantitative e statistiche sull’istanza della base di dati, mentre altre tecniche sfruttano le propriet`a strutturali degli ipergrafi delle interrogazioni. I nostri sforzi si sono rivolti in quest’ultima direzione estendendo il metodo di hypertree decomposition, considerato al momento il pi`u potente tra quelli strutturali. Questa nuova versione, chiamata query-oriented hypertree decomposition, mira a gestire esplicitamente le variabili di output e gli operatori aggregati. Basandoci su queste nozioni, `e stato implementato un ottimizzatore ibrido. Esso pu`o essere utilizzato dai DBMS correntemente disponibili per poter calcolare i piani di esecuzione per le interrogazioni. Tale prototipo `e stato integrato nel noto DBMS open source PostgreSQL. In fine questa estensione `e stata validata attraverso una intensa fase sperimentale, portata avanti con PostgreSQL ed un noto DBMS commerciale, che mostra come entrambi i sistemimigliorino significativamente le loro prestazioni utilizzando le hypertree decomposition per l’ottimizzazione delle interrogazioni. 3 (2) Tecniche per l’integrazione di sorgenti informative Per integrazione di informazioni si intende il problema di combinare i dati residenti in varie sorgenti informative, fornendo agli utenti una vista unificata di questi dati, chiamata global schema. Il nostro lavoro `e stato svolto all’interno del progetto INFOMIX. Il suo scopo principale `e stato quello di fornire tecniche avanzate e metodologie innovative per per gli information integration systems. In breve, il progetto ha sviluppato una teoria, comprendente un modello esauriente ed algoritmi per l’integrazione delle informazioni ed l’implementazione di un prototipo di un sistema knowledge based traminte l’utilizzo della logica computazionale che integri i risultati della ricerca sull’acquisizione e la trasformazione dei dati. Un’attenzione speciale `e stata dedicata alla definizione di un meccanismo per l’interazione dichiarativa da parte dell’utente e alle tecniche per la gestione di dati semistrutturati e sorgenti di dati incomplete o inconsistenti. (3) Tecniche per il mining di processi Nel contesto della enterprise automation, il process mining `e recentemente emerso come uno strumento utilissimo per l’analisi e la progettazione di processi di business complessi. Lo scenario tipico per il process mining `e dato da un insieme di tracce che registrano, tramite un sistema transazionale, le attivit`a svolte durante pi`u esecuzioni di un processo e dall’obiettivo ricavare inmaniera (semi)automatica un modello che possa spiegare tutti gli episodi registrati nelle tracce. Noi abbiamo sviluppato una Suite per le applicazioni del process mining con un’architettura aperta ed estendibile che introduce tre elementi innovativi per soddisfare i desiderata di flessibilit`a e scalabilit`a che sorgono negli scenari industriali attuali. • Il concetto di “flusso di mining”, i.e., essa permette di specificare delle catene di mininig complesse basate sulla connessione di task elementari. • La costruzione di applicazioni interattive basate sulla possibilit`a di personalizzare tipi di dati, algoritmi e l’interfaccia grafica utilizzata per l’analisi. • Scalabilit`a su grandi moli di
Answer Set Programming with Functions
(2014-04-01) Cozza, Susanna; Leone, Nicola
L’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 funzione
Answer set programming:development tols and applications to tourism
(2015-12-15) Nardi, Barbara; Leone, Nicola; Terracina, Giorgio
Answer Set Programming (ASP) is a declarative rule–based programming paradigm for knowledge representation and declarative problem–solving. The idea of ASP is to represent a given computational problem by using a logic program, i.e., a set of logic rule, such that its answer sets correspond to solutions, and then, use an answer set solver to find such solutions. Logic programming paradigms have received renewed interest in recent years, as demonstrated by emerging applications in many different areas of computer science, as well as industry. Due to this renewed interest an increased level of activity in the area has been registered which involved new partitioners both from academia and industry. The development of such applications has provided important information on the real potentials of this programming paradigm, especially concerning the capability of solving complex problems in practice; moreover, application developers highlighted some critical issues to be addressed to make ASP more effective and easy to use ASP in real-world. This thesis offers several contributions in this context can be summarized as follows: (i) The development of two applications of ASP in a specific industrial field; (ii) The design and implementation of new development tools for ASP. Concerning point (i), the thesis addresses two issues considered relevant in the tourism industry. The first is known in the literature as the problem of (semi- )automatic allotment of package tours; and the second is the intelligent management of personalized newsletters for customers of travel agency. The ASP-based solutions presented in the thesis confirm that ASP is an effective tool for solving complex real-world problems. Concerning point (ii), the thesis describes two new development tools that extend ASPIDE, a well-known integrated development environment for ASP. The first tool aims at making easier the writing of logic programs for novice programmers and is particularly suitable for those who prefer visual programming tools. In particular, the user can “ draw ” an ASP program composing graphically the logic rules. The second development tool described in the thesis answers a need arising in the scientific communities that study the usage of logic programming, and its extensions, for reasoning and querying ontologies. The goal is to integrate editing tools for ontologies with tools for the development/generation of logic programs. To this end, the thesis proposes a tool that connects two well-known development environments in the two fields,ASPIDE and Prot´eg´e, in an integrated environment. The main contributions presented in this thesis have been published in the following research papers: Barbara Nardi, Kristian Reale, Francesco Ricca, Giorgio Terracina: An Integrated Environment for Reasoning over Ontologies via Logic Programming. Web Reasoning and Rule Systems - 7th International Conference, RR 2013, Mannheim, Germany, July 27-29, 2013. (LNCS – Vol. 7994 – Springer – Pg. 253-258). Barbara Nardi: A Visual Syntax for Answer Set Programming. Web Reasoning and Rule Systems - 8th International Conference, RR 2014, Athens, Greece, September 15-17, 2014. (LNCS – Vol. 8741 – Springer – Pg.249- 250). Carmine Dodaro, Nicola Leone, Barbara Nardi, Francesco Ricca: Allotment Problem in Travel Industry: A Solution Based on ASP. Web Reasoning and Rule Systems - 9th International Conference, RR 2015, Berlin, Germany, August 4-5, 2015. (LNCS – Vol. 9209 – Springer – Pg. 77-92).
Capitulation and stabilization in various aspects of Iwasawa theory for Zp-extensions
(2013-11-25) Caldarola, Fabio; Bandini, Andrea; Leone, Nicola
Cellular automata for modeling and simulating complex phenomena : lahars
(2015-12-15) Machado Sotomayor, Guillermo Edvin; Salvatore Di Gregori, Salvatore; Lupiano, Valeria; Leone, Nicola
Lahars represent one of the most destructive natural disasters regarding the loss of human lives and property damage in their path. Lahars are very complex surface flows of two types: primary lahars originated directly from eruptive volcanic activity, and secondary lahars originated in post-eruptive events or quiescent periods. Lahars are a complex combination of many interrelated processes besides the process of surface flow: rainwater percolation in the soil (secondary lahars), volcanic stratum erosion, water inclusion and extrusion in lahar, ice melting and mixing with volcanic emissions (primary lahars). Evaluating the hazard posed by lahars constitutes a significant challenge within the framework of modeling and simulation of complex systems for reducing hazard in many, sometimes very populous, inhabited areas next some dangerous volcanoes. A variety of approaches has been taken to modeling the behaviors of lahars and the hazards posed to downstream communities: empirical models based on smart correlations of phenomenon observables, simple rheological and hydrological models and Partial Differential Equations (approximating numerical methods of fluid dynamics). Cellular Automata (CA) represent an alternative approach for modeling and simulating complex systems evolving on the base of local interactions of their elementary components. Lahars may be classified as such a type of phenomenon. Moreover, a CA modeling methodology has been developed for simulating surface flows. CA are a parallel computational paradigm for modeling complex systems by defining ‘simple’ laws at a local level that generate a global ‘complex’ evolution. The research, reported in this thesis, adopts a Multicomponent (or Macroscopic) Cellular Automata (MCA) approach that was applied to other complex surface flows. The model LLUNPIY has been developed in this frame, and successful simulations of real events were performed. The goal of this thesis has been to develop a CA model, LLUNPIY (Lahar modeling by Local rules based on an UNderlying PIck of Yoked processes, from the Kichwa word llunp’iy meaning flood), which is based on the CA semi-empirical approach to macroscopic phenomena of Di Gregorio and Serra, in order to simulate the complex dynamics of lahars, taking into account experience of models like SCIDDICA, SCIARA, PYR, VALANCA and SCAVATU.
Computational tasks in answer set programming: algorithms and implementation
(2014-12-01) Dodaro, Carmine; Leone, Nicola; Ricca, Francesco
L’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.
Concentration and asymptotic behavior of solutions for some singularly perturbed mixed problems
(2014-05-27) Montoto, Luigi; Leone, Nicola; Canino, Annamaria; Peral, Ireneo
Convex tomography in dimension two and three
(2014-05-27) Dicosta, Marina; Leone, Nicola; Volcic, Aljosa
In this thesis we investigate a problem which is part of Geometric Tomography. Geometric Tomography is a branch of Mathematics which deals with the determination of a convex body (or other geometric objects) in n from the measure of its sections, projections, or both. In particular, it is focused on finding conditions sufficient to establish the minimum number of point X-rays needed to determine uniquely a convex body in n. The interest for this particular mathematical subject has its roots in the studies related to Tomography. Nowadays it is rare that someone has never heard of CAT scan (Computed Assisted Tomography). This medical diagnostic technique, born in the late 70s, allows us to reconstruct the image of a three-dimensional object by a large number of projections at different directions. It is useful to emphasize that CAT is a direct application of a pure mathematical instrument known as ‘the Radon transform”. From the mathematical point of view, the question of when a convex body, a compact convex set with nonempty interior, can be reconstructed by means of its X-ray, arose from problems (published in 1963) posed by Hammer in 1961 during a Symposium on convexity: « Suppose there is a convex hole in an otherwise homogeneous solid and that X-ray pictures taken are so sharp that the “darkness” at each point determines the length of a chord along an X-ray line. (No diffusion please). How many pictures must be taken to permit exact reconstruction of the body if: (a) The X-rays issue from a finite point source? (b) The X-rays are assumed parallel? » A convex body is a convex compact set with nonempty interior. We distinguish between two problems, according to the X-rays are at a finite point i ii source or at infinity. We are searching which properties a set of directions U must fulfill, in order to determine uniquely a convex body K by means of its (either parallel or point) X-rays, in the directions of U. When U is an infinite set then this reconstruction is possible and this follows from general theorems regarding the inversion of the Radon transform. This thesis consists of two parts. The first (Chapter 3) is concerned with the determination of a planar convex body from its i-chord functions, while the second part (Chapter 4) generalizes the planar results to the three-dimensional case. The main results provide a partial answer to the problem posed by R. J. Gardner: “How many point X-rays are needed to determine a convex body in n?” We use two analytic tools both considered in geometric tomography for the first time by K. J. Falconer. One is the i-chord function, which is related through the Funk theorem to the measures of the i-dimensional sections, when i is a positive integer. The other tool, inspired by a paper by D. C. Solmon, suggested the introduction of a kind of “Cavalieri Principle” for point X-rays, and has been later on extended to other dimensions and real values of i. The i-chord functions allow to translate in analytical form the information given by the ith section functions. Therefore, from an analytical point of view we have the following problem: “Suppose that K ! n is a convex body and let ph be some noncollinear points (some of them are possibly at infinity). Suppose, moreover, that we are given the i-chord functions at the points ph, with i " . Is K then uniquely determined among all convex bodies?” The i-chord functions !i,K can be seen as a generalization of the radial function of the convex body K. The latter is the function that gives the signed distance from the origin to the boundary of K. For integer values of the parameter i, the i-chord function is closely linked to the ith section function of a convex body, that is the function assigning to each subspace of dimension i the i-dimensional measure. When i = 1, the 1st section function coincides with the 1-chord function, that is the point X-ray of the convex body at the origin. In Chapter 3 we consider two planar problems. One problem consists of the determination of a planar convex body K from the i-chord functions, for i > 0, at two points when the line l passing through p1 and p2 meets the interior of K and the two points p1 and p2 are both exterior or interior to K. If the line l supports K, then the results hold for i # 1. The second result concerns the determination of a planar iii convex body K from its i-chord functions at three noncollinear points for 0 < i < 2. Chapter 4 deals with the problem of determining a three-dimensional convex body K from the i-chord functions at three noncollinear points non belonging
CORE: an intelligent trasportation systems in Calabria
(2017-02-22) Santoro, Francesco; Leone, Nicola; Laganà, Demetrio; Musmanno, Roberto
Datalog with existential quantifiers: an optimal trade-off between expressiveness and scalability
(2012-11-11) Veltri, Pierfrancesco; Leone, Nicola; Terracina, Giorgio
Ontologies and rules play a central role in the development of the Semantic Web. Recent research in this context focuses especially on highly scalable formalisms for the Web of Data, which may highly benefit from exploiting database technologies. In particular, Datalog∃ is the natural extension of Datalog, allowing existentially quantified variables in rule heads. This language is highly expressive and enables easy and powerful knowledge-modeling, but the presence of existentially quantified variables makes reasoning over Datalog∃ undecidable, in the general case. The results in this thesis enable powerful, yet decidable and efficient reasoning (query answering) on top of Datalog∃ programs. On the theoretical side, we define the class of parsimonious Datalog∃ programs, and show that it allows of decidable and efficiently-computable reasoning. Unfortunately, we can demonstrate that recognizing parsimony is undecidable. However, we single out Shy, an easily recognizable fragment of parsimonious programs, that significantly extends both Datalog and Linear Datalog∃. Moreover, we show that Shy preserves the same (data and combined) complexity of query answering over Datalog, although the addition of existential quantifiers. On the practical side, we implement a bottom-up evaluation strategy for Shy programs inside the DLV system, enhancing the computation by a number of optimization techniques. The resulting system is called DLV∃– a powerful system for answering conjunctive queries over Shy programs, which is profitably applicable to ontology-based query answering. Moreover, we design a rewriting method extending the well-known Magic-Sets technique to any Datalog∃ program. We demonstrate that our rewriting method preserves query equivalence on Datalog∃, and can be safely applied to Shy programs. We therefore incorporate the Magic- Sets method in DLV∃. Finally, we carry out an experimental analysis assessing the positive impact of Magic-Sets on DLV∃, and the effectiveness of the enhanced DLV∃ system compared to a number of state-of-the-art systems for ontologybased query answering.
Declarative solutions for the the Manipulation of Articulated Objects Using Dual-Arm Robots
(Università della Calabria, 2020-03-17) Bertolucci, Riccardo; Leone, Nicola; Maratea, Marco; Mastrogiovanni, Fulvio
The manipulation of exible object is of primary importance in industry 4.0 and in home environments scenarios. Traditionally, this problem has been tackled by developing ad-hoc approaches, that lack of exibility and portability. We propose an approach in which a exible object is modelled as an articulated object, or rather, a set of links connect via joints. In this thesis we present a framework based on Answer Set Programming (ASP) for the automated manipulation of articulated objects in a robot architecture. In particular, ASP is employed for representing the con guration of the articulated object, for checking the consistency of the knowledge base, and for generating the sequence of manipulation actions. The framework is exempli ed and validated on the Baxter dual-arm manipulator on a simple reference scenario in which we carried out di erent experiments analysing the behaviours of di erent strategies for the action planning module. Our aim is to have an understanding of the performances of these approaches with respect to planning time and execution time as well. Then, we extend such scenario for having a higher accuracy of the setup, and to introduce a few constraints in robot actions execution to improve their feasibility. Given the extended scenario entails a high number of possible actions that can be fruitfully combined, we exploit macro actions from automated planning in the module that generates the sequence of actions, in order to deal with this extended scenario in a more e ective way. Moreover, we analyse the possibilities of mixed encodings with both simple actions and macro actions from automated planning in di erent "concentrations". We nally validate the framework also on this extended scenario, con rming the applicability of ASP also in this complex context, and showing the usefulness of macro actions in this robotics application.
Design and implementation of a modern ASP grounder
(2018-01-19) Zangari, Jessica; Leone, Nicola; Calimeri, Francesco; Perri, Simona
Answer Set Programming (ASP) is a declarative programming paradigm proposed in the area of non-monotonic reasoning and logic programming in the late '80 and early '90. Thanks to its expressivity and capability of dealing with incomplete knowledge, ASP that became widely used in AI and recognized as a powerful tool for Knowledge Representation and Reasoning (KRR). On the other hand, its high expressivity comes at the price of a high computational cost, thus requiring reliable and high-performance implementations. Throughout the years, a signi cant e ort has been spent in order to de ne techniques for an e cient computation of its semantics. In turn, the availability of e cient ASP systems made ASP a powerful tool for developing advanced applications in many research areas as well as in industrial contexts. Furthermore, a signi cant amount of work has been carried out in order to extend the basic language and ease knowledge representation tasks with ASP, and recently a standard input language, namely ASP-Core-2, has been de ned, also with the aim of fostering interoperability among ASP systems. Although di erent approaches for the evaluation of ASP logic programs have been proposed, the canonical approach, which is adopted in mainstream ASP systems, mimics the de nition of answer set semantics by relying on a grounding module (grounder), that generates a propositional theory semantically equivalent to the input program, coupled with a subsequent module (solver ) that applies propositional techniques for generating its answer sets. The former phase, called grounding or instantiation, plays a key role for the successful deployment in real-world contexts, as in general the produced ground program is potentially of exponential size with respect to the input program, and therefore the subsequent solving step, in the worst case, takes exponential time in the size of the input. To mitigate these issues, modern grounders employ smart procedures to obtain ground programs signi cantly smaller than the theoretical instantiation, in general. This thesis focuses on the ex-novo design and implementation of a new modern and e cient ASP instantiator. To this end, we study a series of techniques geared towards the optimization of the grounding process, questioning the techniques employed by modern grounders with the aim of improving them and introducing further optimization strategies, which lend themselves to the integration into a generic grounder module of a traditional ASP system following a ground & solve approach. In particular, we herein present the novel system I-DLV that incorporates all these techniques leveraging on their synergy to perform an e cient instantiation. The system features full support to ASP-Core-2 standard language, advanced exibility and customizability mechanisms, and is endowed with extensible design that eases the incorporation of language upi dates and optimization techniques. Moreover, its usage is twofold: besides being a stand-alone grounder, it is also a full- edged deductive database engine. In addition, along with the solver wasp it has been integrated in the new version of the widespread ASP system DLV recently released.
A DLP-Based System for Ontology Representation and Reasoning
(2012-11-09) Gallucci, Lorenzo; Leone, Nicola; Talia, Domenico
In 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.
DLVDB An ASP System for Data Intensive ApplicationsRisorsa elettronica
(2014-04-01) Panetta, Claudio; Leone, Nicola; Terracina, Giorgio
La 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.
Domain specific languages for parallel numerical modeling on structured grids
(2019-01-17) De Rango, Alessio; Leone, Nicola; D'Ambrosio, Donato; Spataro, William; Mudalige, Gihan
High performance computing (HPC) is undergoing a period of enormous change. Due to the di culties in increasing clock frequency inde nitely (i.e., the breakdown of Dennard's scaling and power wall), the current direction is towards improving performance through increasing parallelism. However, there is no clear consensus yet on the best architecture for HPC, and di erent solutions are currently employed. As a consequence, applications targeting a given architecture can not be easily adapted to run on alternative solutions, since this would require a great e ort due to the need to deal with platform-speci c details. Since it is not known a priori which HPC architecture will prevail, the Scienti c Community is looking for a solution that could tackle the above mentioned issue. A possible solution consists in the adoption of a high-level abstraction development strategy based on Domain Speci c Languages (DSLs). Among them, OpenCAL (Open Computing Abstraction Layer) and OPS (Oxford Parallel Structured) have been proposed as domain speci c C/C++ data parallel libraries for structured grids. The aim of these libraries is to provide an abstract computing model able to hide any parallelization detail by targeting, at the same time, di erent current (and possibly future) parallel architectures. In this Thesis, I have contributed to the design and development of both the OpenCAL and OPS projects. In particular, my contribution to OpenCAL has regarded the development of the single-GPU and multi-GPU/multi-node components, namely OpenCAL-CL and OpenCAL-CLM, while my contribution to OPS has regarded the introduction of the OpenMP 4.0/4.5 support, as an alternative to OpenCL, CUDA and OpenACC, for exploiting modern many-core computing systems. Both the improved DSLs have been tested on di erent benchmarks, among which a fractal set generator, a graphics lter routine, and three di erent uid- ows applications, with more than satisfying results. In particular, OpenCAL was able to e ciently scale over larger computational domains with respect to its original implementation, thanks to the new multi-GPU/multi-node capabilities, while OPS was able to reach near optimal performance using the high-level OpenMP 4.0/4.5 speci cations on many-core accelerators with respect to the alternative low-level CUDA-based version.
Dyadic TGDs - A new paradigm for ontological query answering
(Università della Calabria, 2022-03-11) Marte, Cinzia; Greco, Gianluigi; Manna, Marco; Guerriero, Francesca; Leone, Nicola
Ontology-BasedQueryAnswering(OBQA)consistsinqueryingdata– bases bytakingontologicalknowledgeintoaccount.Wefocusona logical frameworkbasedonexistentialrulesor tuple generatingdepen- dencies (TGDs), alsoknownasDatalog±, whichcollectsthebasicde- cidable classesofTGDs,andgeneralizesseveralontologyspecification languages. While thereexistlotsofdifferentclassesintheliterature,inmost cases eachofthemrequiresthedevelopmentofaspecificsolverand, only rarely,thedefinitionofanewclassallowstheuseofexisting systems. Thisgapbetweenthenumberofexistentparadigmsandthe numberofdevelopedtools,promptedustodefineacombinationof Shy and Ward (twowell-knownclassesthatenjoygoodcomputational properties)withtheaimofexploitingthetooldevelopedfor Shy. Nevertheless,studyinghowtomergethesetwoclasses,wehavereal- ized thatitwouldbepossibletodefine,inamoregeneralway,the combinationofexistingclasses,inordertomakethemostofexisting systems. Hence, inthiswork,startingfromtheanalysisofthetwoaforemen- tioned existingclasses,wedefineamoregeneralclass,named Dyadic TGDs, thatallowstoextendinauniformandelegantwayallthede- cidable classes,whileusingtheexistentrelatedsystems.Atthesame time, wedefinealsoacombinationof Shy and Ward, named Ward+, and weshowthatitcanbeseenasaDyadicsetofTGDs. Finally,tosupportthetheoreticalpartofthethesis,weimplementa BCQ evaluationalgorithmfortheclass Ward+, thattakesadvantage of anexistingsolverdevelopedfor Shy.
Eccient evaluation of disjunctive logic programs
(2014-03-31) Catalano, Gelsomina; Leone, Nicola; Perri, Simona
Agli 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.
Enhancing and Applying Answer Set Programming: Lazy Constraints, Partial Compilation and Question Answering
(2019-01-17) Cuteri, Bernardo; Leone, Nicola; Ricca, Francesco
This work is focused on Answer Set Programming (ASP), that is an expressive formalism for Knowledge Representation and Reasoning. Over time, ASP has been more and more devoted to solving real-world problems thanks to the availability of e cient systems. This thesis brings two main contributions in this context: (i) novel strategies for improving ASP programs evaluation, and (ii) a real-world application of ASP to Question Answering in Natural Language. Concerning the rst contribution, we study some cases in which classical evaluation fails because of the so-called grounding bottleneck. In particular, we rst focus on cases in which the standard evaluation strategy is ine ective due to the grounding of problematic constraints. We approach the problem using custom propagators and lazy instantiators, proving empirically when this solution is e ective, which is an aspect that was never made clear in the existing literature. Despite the development of propagators can be effective, it has two main disadvantages: it requires deep knowledge of the ASP systems, and the resulting solution is not declarative. We propose a technique for overcoming these issues which we call program compilation. In our approach, the propagators for some of the logic rules (not only for the constraints) of a program are generated automatically by a compiler. We provide some su cient conditions for identifying the rules that can be compiled in an approach that ts a propagator-based system architecture. An empirical analysis shows the performance bene ts obtained by introducing (partial) compilation into ASP programs evaluation. To the best of our knowledge, this is the rst work on compilation-based techniques for ASP. Concerning the second part of the thesis, we present the development of a Natural Language Question Answering System whose core is based on ASP. The proposed system gradually transforms input questions into SPARQL queries that are executed on an ontological knowledge base. The system integrates several state-of-the NLP models and tools with a special focus on the Italian language and the Cultural Heritage domain. ASP is used to classify questions from a syntactical point of view. The resulting system is the core module of the PIUCULTURA project, funded by the Italian Ministry of Economic Development, that has the aim to devise a system for promoting and improving the fruition of Cultural Heritage.
Extending the ASP System DLVDB to Support Complex Terms and Procedural Sub-tasks
(2014-03-31) De Francesco, Erika; Terracina, Giorgio; Leone, Nicola
In 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.