Dipartimento di Matematica e Informatica - Tesi di Dottorato

Permanent URI for this collectionhttps://lisa.unical.it/handle/10955/103

Questa collezione raccoglie le Tesi di Dottorato afferenti al Dipartimento di Matematica e Informatica dell'Università della Calabria.

Browse

Now showing 1 - 20 of 76

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).
Arsenic Ore Mixture Froth Image Generation with Neural Networks and a Language for Declarative Data Validation
(Università della Calabria, 2022-04-14) Zamayla, Arnel; Greco, Gianluigi; Alviano, Mario; Dodaro, Carmine
Computer vision systems that measure froth flow velocities and stability designed for flotation froth image analysis are well established in industry, as they are used to control material recovery. However flotation systems that has limited data has not been explored in the same fashion bearing the fact that big data tools like deep convolutional neural networks require huge amounts of data. This lead to the motivation of the research reported in the first part of this thesis, which is to generate synthetic images from limited data in order to create a froth image dataset. The image synthesis is possible through the use of generative adversarial network. The performance of human experts in this domain in identifying the original and synthesized froth images were then compared with the performance of the models. The models exhibited better accuracy levels by average on the tests that were performed. The trained classifier was also compared with some of the established neural network models in the literature like the AlexNet, VGG16 ang ResNet34. Transfer learning was used as a method for this purpose. It also showed that these pretrained networks that are readily available have better accuracy by average comapared to trained experts. The second part of this thesis reports on a language designed for data validation in the context of knowledge representation and reasoning. Specifically, the target language is Answer Set Programming (ASP), a logic-based programming language widely adopted for combinatorial search and optimization, which however lacks constructs for data validation. The language presented in this thesis fulfills this gap by introducing specific constructs for common validation criteria, and also supports the integration of consolidated validation libraries written in Python. Moreover, the language is designed so to inject data validation in ordinary ASP programs, so to promote fail-fast techniques at coding time without imposing any lag on the deployed system if data are pretended to be valid.
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.
Deep Learning and Graph Theory for Brain Connectivity Analysis in Multiple Sclerosis
(Università della Calabria, 2020-01-16) Marzullo, Aldo; Leone, Nicola; Calimeri, Francesco; Terracina, Giorgio;
Multiple sclerosis (MS) is a chronic disease of the central nervous system, leading cause of nontraumatic disability in young adults. MS is characterized by inflammation, demyelination and neurodegenrative pathological processes which cause a wide range of symptoms, including cognitive deficits and irreversible disability. Concerning the diagnosis of the disease, the introduction of Magnetic Resonance Imaging (MRI) has constituted an important revolution in the last 30 years. Furthermore, advanced MRI techniques, such as brain volumetry, magnetization transfer imaging (MTI) and diffusion-tensor imaging (DTI) are nowadays the main tools for detecting alterations outside visible brain lesions and contributed to our understanding of the pathological mechanisms occurring in normal appearing white matter. In particular, new approaches based on the representation of MR images of the brain as graph have been used to study and quantify damages in the brain white matter network, achieving promising results. In the last decade, novel deep learning based approaches have been used for studying social networks, and recently opened new perspectives in neuroscience for the study of functional and structural brain connectivity. Due to their effectiveness in analyzing large amount of data, detecting latent patterns and establishing functional relationships between input and output, these artificial intelligence techniques have gained particular attention in the scientific community and is nowadays widely applied in many context, including computer vision, speech recognition, medical diagnosis, among others. In this work, deep learning methods were developed to support biomedical image analysis, in particular for the classification and the characterization of MS patients based on structural connectivity information. Graph theory, indeed, constitutes a sensitive tool to analyze the brain networks and can be combined with novel deep learning techniques to detect latent structural properties useful to investigate the progression of the disease. In the first part of this manuscript, an overview of the state of the art will be given. We will focus our analysis on studies showing the interest of DTI for WM characterization in MS. An overview of the main deep learning techniques will be also provided, along with examples of application in the biomedical domain. In a second part, two deep learning approaches will be proposed, for the generation of new, unseen, MRI slices of the human brain and for the automatic detection of the optic disc in retinal fundus images. In the third part, graph-based deep learning techniques will be applied to the study of brain structural connectivity of MS patients. Graph Neural Network methods to classify MS patients in their respective clinical profiles were proposed with particular attention to the model interpretation, the identification of potentially relevant brain substructures, and to the investigation of the importance of local graph-derived metrics for the classification task. Semisupervised and unsupervised approaches were also investigated with the aim of reducing the human intervention in the pipeline.
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.
Distributed Optimization Over Large-Scale Systems for Big Data Analytics
(Università della Calabria, 2020-01-17) Shahbazian, Reza; Leone, Nicola; Grandinetti, Lucio; Guerriero, Francesca
A large-scale system is defined as one that supports multiple, simultaneous users who access the core functionality through some network. Nowadays, enormous amount of data is continually generated at unprecedented and ever-increasing scales. Large-scale data sets are collected and studied in numerous domains, from engineering sciences to social networks, commerce, bimolecular research, and security. Big Data is a term applied to data sets whose size or type is beyond the ability of traditional relational databases to capture, manage, and process with acceptable latency. Usually, Big Data has one or more of the characteristics including high volume, high velocity, or high variety. Big Data challenges include capturing data, data storage, data analysis, search, sharing, transfer, visualization, querying, updating, information privacy and data source. Generally, Big Data comes from sensors, devices, video or audio, networks, log files, transactional applications, web, and social media, in a very large-scale. Big Data is impossible to analyze by using traditional central methods and therefore, new distributed models and algorithms are needed to process the data. In this thesis, we focus on optimization algorithms for Big Data application. We review some of the recent machine learning, convex and non-convex, heuristic and stochastic optimization techniques and available tools applied to Big Data. We also propose a new distributed and decentralized stochastic algorithm for Big Data analytics. Our proposed algorithm is fully distributed to decide large-scale networks and data sets. The proposed method is scalable to any network configuration, is near real-time (in each iteration, a solution is provided although it might not be the optimum one) and more critical, robust to any missing data or communication failures. We evaluate the proposed method by a practical example and simulations on cognitive radio networks. Simulation results confirmed that the proposed method is efficient in terms of accuracy and robustness. We assume that the distributed data-sources should be capable of processing their data and communicate with neighbor sources to find the network objective as an optimal decision. Some challenges are introduced by new technologies such as 5G or high-speed wireless data transfer, including imperfect communications that damage the data. We propose an optimal algorithm that uses optimal weighting to combine the shared data coming from neighbors. This optimal weight improves the performance of the decision-making algorithm in terms of error and convergence rate. We evaluate the performance of the proposed algorithm mathematically and introduce the step-sized conditions that guaranteed the convergence of the proposed algorithm. We use computer simulations to evaluate the network error. We prove that in a network diagram with ten datasources, the network performance of the proposed algorithm outperforms some of the known optimal solutions such as Metropolis and adaptive combination. Keywords: Optimization, Big Data, Large-Scale, Distributed, Optimal Weight.
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.
Dynamic magic sets
(2010) Alviano, Mario; Lceone, Nicola; Faber, Wolfgang
Disjunctive Datalog with stable model semantics is a rule–based language for knowledge representation and common sense reasoning that also allows to use queries for checking the presence of specific atoms in stable models. Expressive- ness is a strength of the language, which indeed captures the second level of the polynomial hierarchy. However, because of this high expressive power, evalu- ating Disjunctive Datalog programs and queries is inherently nondeterministic. In fact, Disjunctive Datalog computations are typically characterized by two distinct phases. The first phase, referred to as program instantiation, is deter- ministic and associates input programs with equivalent ground programs; only deterministic knowledge is inferred in this phase. The second phase, referred to as stable model search, is nondeterministic and computes stable models of instantiated programs. Many query optimization techniques have been proposed in the literature. Among them are Magic Sets, originally introduced for standard Datalog pro- grams. Program instantiation is sufficient for computing the semantics of stan- dard Datalog programs because only deterministic knowledge can be represented in this case. For this reason, the original Magic Set technique is only focused on the optimization of program instantiation. Dynamic Magic Sets are an exten- sion of the technique that takes into account the nondeterministic knowledge encoded into Disjunctive Datalog programs. In fact, in addition to the standard optimization of program instantiation, Dynamic Magic Sets provide further op- timization potential to the subsequent stable model search. In this thesis, Dynamic Magic Sets are proved to be sound and complete for stratified and super–coherent programs. To this end, a strong relationship between magic atoms and unfounded sets is highlighted. Dynamic Magic Sets are also used for proving decidability of reasoning for a class of programs with uninterpreted function symbols. In particular, it is shown that the application of Dynamic Magic Sets to finitely recursive queries generates finitely ground programs, for which decidability of reasoning has been established in the liter- ature. Dynamic Magic Sets have been implemented in a prototype extending DLV, a state–of–the–art system for Disjunctive Datalog programs and queries. The effectiveness of Dynamic Magic Sets has been assessed by experimenting with the prototype system. Experimental results confirm that Dynamic Magic Sets can provide significant, possibly exponential, performance gains.