Abstract DLV2 is an AI tool for knowledge representation and reasoning that supports answer set programming (ASP) – a logic-based declarative formalism, successfully used in both academic and industrial applications. Given a logic program modeling a computational problem, an execution of DLV2 produces the so-called answer sets that correspond one-to-one to the solutions to the problem at hand. The computational process of DLV2 relies on the typical ground & solve approach, where the grounding step transforms the input program into a new, equivalent ground program, and the subsequent solving step applies propositional algorithms to search for the answer sets. Recently, emerging applications in contexts such as stream reasoning and event processing created a demand for multi-shot reasoning: here, the system is expected to be reactive while repeatedly executed over rapidly changing data. In this work, we present a new incremental reasoner obtained from the evolution of DLV2 toward iterated reasoning. Rather than restarting the computation from scratch, the system remains alive across repeated shots, and it incrementally handles the internal grounding process. At each shot, the system reuses previous computations for building and maintaining a large, more general ground program, from which a smaller yet equivalent portion is determined and used for computing answer sets. Notably, the incremental process is performed in a completely transparent fashion for the user. We describe the system, its usage, its applicability, and performance in some practically relevant domains.

Automating acts on touch surfaces opens a range of possibilities for researching and experimenting with hybrid AI approaches. In this paper, we propose a delta robot capable of playing match-3 games and ball-sorting puzzles by acting on mobile phones. The robot recognizes objects of different colors and shapes through a vision module, is capable of making strategic decisions based on declarative models of the game's rules and of the game playing strategy, and features an effector that executes moves on physical devices. Our solution integrates multiple AI methods, including vision processing and answer set programming. Helpful and reusable infrastructure is provided: the vision task is facilitated, while robot motion control is inherently simplified by the usage of a delta robot layout. We illustrate the components of our robotic application and how they were integrated. Then, we briefly showcase how recognition and general knowledge can be modeled and implemented, by overviewing the implementation of representative games. We argue that our application provides potential for KR and robotics to be combined in creative ways, and offers itself as a general controlled environment where to experiment with forms of hybrid reasoning, while relieving from implementation details.

Declarative methods such as Answer Set Programming show potential in cutting down development costs in commercial videogames and real-time applications in general. Many shortcomings, however, prevent their adoption, such as performance and integration gaps. In this work we illustrate our ThinkEngine, a framework in which a tight integration of declarative formalisms within the typical game development workflow is made possible in the context of the Unity game engine. ThinkEngine allows to wire declarative AI modules to the game logic and to move the computational load of reasoning tasks outside the main game loop using an hybrid deliberative/reactive architecture. In this paper, we illustrate the architecture of the ThinkEngine and its role both at design and run-time. Then we show how to program declarative modules in a proof-of-concept game, and report about performance and related work.

DLV2 is an AI tool for Knowledge Representation and Reasoning which supports Answer Set Programming (ASP) – a logic-based declarative formalism, successfully used in both academic and industrial applications. Given a logic program modelling a computational problem, an execution of DLV2 produces the so-called answer sets that correspond one-to-one to the solutions. The computational process relies on the typical Ground&Solve approach where the grounding step transforms the input program into a new, equivalent ground program, and the subsequent solving step applies propositional algorithms to search for the answer sets. Recently, emerging applications in contexts such as stream reasoning and event processing demand for multi-shot reasoning: here, the system is expected to be reactive while repeatedly executed over rapidly changing data. In this work, we present a new incremental reasoner obtained from the evolution of DLV2 towards multi-shot reasoning. Rather than restarting the computation from scratch, the system remains alive and incrementally handles the internal grounding process: in a completely transparent fashion for the user, at each shot, it reuses previous computations for building and maintaining a large, more general ground program, from which a smaller yet equivalent portion is determined and used for computing answer sets. We describe the system, its usage, its applicability and performance in some practically relevant domains.

Abstract Standardization of solver input languages has been a main driver for the growth of several areas within knowledge representation and reasoning, fostering the exploitation in actual applications. In this document, we present the ASP-CORE-2 standard input language for Answer Set Programming, which has been adopted in ASP Competition events since 2013.

Abstract The repeated execution of reasoning tasks is desirable in many applicative scenarios, such as stream reasoning and event processing. When using answer set programming in such contexts, one can avoid the iterative generation of ground programs thus achieving a significant payoff in terms of computing time. However, this may require some additional amount of memory and/or the manual addition of operational directives in the declarative knowledge base at hand. We introduce a new strategy for generating series of monotonically growing propositional programs. The proposedovergrounded programs with tailoring(OPTs) can be updated and reused in combination with consecutive inputs. With respect to earlier approaches, ourtailored simplificationtechnique reduces the size of instantiated programs. A maintained OPT slowly grows in size from an iteration to another while the update cost decreases, especially in later iterations. In this paper we formally introduce tailored embeddings, a family of equivalence-preserving ground programs which are at the theoretical basis of OPTs and we describe their properties. We then illustrate an OPT update algorithm and report about our implementation and its performance.

Abstract Repeated executions of reasoning tasks for varying inputs are necessary in many applicative settings, such as stream reasoning. In this context, we propose an incremental grounding approach for the answer set semantics. We focus on the possibility of generating incrementally larger ground logic programs equivalent to a given non-ground one; so calledovergrounded programscan be reused in combination with deliberately many different sets of inputs. Updating overgrounded programs requires a small effort, thus making the instantiation of logic programs considerably faster when grounding is repeated on a series of inputs similar to each other. Notably, the proposed approach works “under the hood”, relieving designers of logic programs from controlling technical aspects of grounding engines and answer set systems. In this work we present the theoretical basis of the proposed incremental grounding technique, we illustrate the consequent repeated evaluation strategy and report about our experiments.

This paper presents the Angry-HEX artificial intelligent agent that participated in the 2013 and 2014 Angry Birds Artificial Intelligence Competitions. The agent has been developed in the context of a joint project between the University of Calabria (UniCal) and the Vienna University of Technology (TU Vienna). The specific issues that arise when introducing artificial intelligence in a physics-based game are dealt with a combination of traditional imperative programming and declarative programming, used for modeling discrete knowledge about the game and the current situation. In particular, we make use of HEX programs, which are an extension of answer set programming (ASP) programs toward integration of external computation sources, such as 2-D physics simulation tools.

Abstract As software systems are getting increasingly connected, there is a need for equipping nonmonotonic logic programs with access to external sources that are possibly remote and may contain information in heterogeneous formats. To cater for this need, hex programs were designed as a generalization of answer set programs with an API style interface that allows to access arbitrary external sources, providing great flexibility. Efficient evaluation of such programs however is challenging, and it requires to interleave external computation and model building; to decide when to switch between these tasks is difficult, and existing approaches have limited scalability in many real-world application scenarios. We present a new approach for the evaluation of logic programs with external source access, which is based on a configurable framework for dividing the non-ground program into possibly overlapping smaller parts called evaluation units. The latter will be processed by interleaving external evaluation and model building using an evaluation graph and a model graph, respectively, and by combining intermediate results. Experiments with our prototype implementation show a significant improvement compared to previous approaches. While designed for hex -programs, the new evaluation approach may be deployed to related rule-based formalisms as well.

Abstract Answer Set Programming (ASP) is a well-established paradigm of declarative programming in close relationship with other declarative formalisms such as SAT Modulo Theories, Constraint Handling Rules, FO(.), PDDL and many others. Since its first informal editions, ASP systems have been compared in the now well-established ASP Competition. The Third (Open) ASP Competition, as the sequel to the ASP Competitions Series held at the University of Potsdam in Germany (2006–2007) and at the University of Leuven in Belgium in 2009, took place at the University of Calabria (Italy) in the first half of 2011. Participants competed on a pre-selected collection of benchmark problems, taken from a variety of domains as well as real world applications. The Competition ran on two tracks: the Model and Solve (M&S) Track, based on an open problem encoding, and open language, and open to any kind of system based on a declarative specification paradigm; and the System Track, run on the basis of fixed, public problem encodings, written in a standard ASP language. This paper discusses the format of the competition and the rationale behind it, then reports the results for both tracks. Comparison with the second ASP competition and state-of-the-art solutions for some of the benchmark domains is eventually discussed.

The realization of the Semantic Web vision, in which computational logic has a prominent role, has stimulated a lot of research on combining rules and ontologies, which are formulated in different formalisms. In particular, combining logic programming with the Web Ontology Language (OWL), which is a standard based on description logics, emerged as an important issue for linking the Rules and Ontology Layers of the Semantic Web. Nonmonotonic description logic programs (dl-programs) were introduced for such a combination, in which a pair(L,P)of a description logic knowledge baseLand a set of rulesPwith negation as failure is given a model-based semantics that generalizes the answer set semantics of logic programs. In this article, we reconsider dl-programs and present a well-founded semantics for them as an analog for the other main semantics of logic programs. It generalizes the canonical definition of the well-founded semantics based on unfounded sets, and, as we show, lifts many of the well-known properties from ordinary logic programs to dl-programs. Among these properties, our semantics amounts to a partial model approximating the answer set semantics, which yields for positive and stratified dl-programs, a total model coinciding with the answer set semantics; it has polynomial data complexity provided the access to the description logic knowledge base is polynomial; under suitable restrictions, it has lower complexity and even first-order rewritability is achievable. The results add to previous evidence that dl-programs are a versatile and robust combination approach, which moreover is implementable using legacy engines.

This paper summarizes our line of research about the introduction of function symbols (functions) in Answer Set Programming (ASP) – a powerful language for knowledge representation and reasoning. The undecidability of reasoning on ASP with functions, implied that functions were subject to severe restrictions or disallowed at all, drastically limiting ASP applicability. We overcame most of the technical difficulties preventing this introduction, and we singled out a highly expressive class of programs with functions (FG-programs), allowing the (possibly recursive) use of function terms in the full ASP language with disjunction and negation. Reasoning on FG-programs is decidable, and they can express any computable function (causing membership in this class to be semi-decidable). We singled out also FD-programs, a subset of FG-programs which are effectively recognizable, while keeping the computability of reasoning. We implemented all results into the DLV system, thus obtaining an ASP system allowing to encode any computable function in a rich and fully declarative KRR language, ensuring termination on every FG program. Finally, we singled out the class of DFRP programs, where decidability of reasoning is guaranteed and Prolog-like functions are allowed.

Ontologies are pervading many areas of knowledge representation and management. To date, most research efforts have been spent on the development of sufficiently expressive languages for the representation and querying of ontologies; however, querying efficiency has received attention only recently, especially for ontologies referring to large amounts of data. In fact, it is still uncertain how reasoning tasks will scale when applied on massive amounts of data. This work is a first step toward this setting: it first shows that Resource Description Framework(Schema) [RDF(S)] ontologies can be expressed, without loss of semantics, into Answer Set Programming (ASP). Then, based on a previous result showing that the SPARQL query language (a candidate W3C recommendation for RDF(S) ontologies) can be mapped to a rule-based language, it shows that efficient querying of big ontologies can be accomplished with a database oriented extension of the well known ASP system DLV, which we recently developed. Results reported in the article show that our proposed framework is promising for the improvement of both scalability and expressiveness of available RDF(S) storage and query systems.

Towards providing a suitable tool for building the Rule Layer of the Semantic Web, hex -programs have been introduced as a special kind of logic programs featuring capabilities for higher-order reasoning, interfacing with external sources of computation, and default negation. Their semantics is based on the notion of answer sets, providing a transparent interoperability with the Ontology Layer of the Semantic Web and full declarativity. In this paper, we identify classes of hex -programs feasible for implementation yet keeping the desirable advantages of the full language. A general method for combining and evaluating sub-programs belonging to arbitrary classes is introduced, thus enlarging the variety of programs whose execution is practicable. Implementation activity on the current prototype is also reported. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We present the system dlvhex, a solver for HEX-programs, which are nonmonotonic logic programs admitting both higher-order atoms as well as external atoms. Higher-order features are widely acknowledged as being useful for various tasks, including meta-reasoning. Furthermore, the possibility to exchange knowledge with external sources in a fully declarative paradigm such as answer-set programming (ASP) becomes increasingly important, in particular in view of applications in the semantic-Web area. Through external atoms, HEX-programs can deal with external knowledge and reasoners of various nature, such as RDF datasets or description-logics knowledge bases

The language of HEX-programs under the answer-set semantics is designed for interoperating with heterogeneous sources via external atoms and for meta-reasoning via higher-order literals in the context of the semantic Web. As an important technique in managing knowledge bases, the notion of forgetting has received increasing interest in the knowledge-representation area. In this paper, we introduce a semantics-based theory of forgetting for HEX-programs and, in turn, for a class of OWL/RDF(S) ontologies which allows to fully employ semantic information in managing ontologies like editing, merging, aligning, and redundancy removal

Information extraction technologies meet the market need for automatic tools for extracting semi-structured information from Web pages. However, pages may change over time due to different reasons, ranging from restyling pages to on-purpose modifications brought about into pages in order to puzzle Web wrappers. In this paper we deal with this latter scenario, by studying the issue of on-purpose wrapper spoiling and its relationship to wrapping. We present an architecture and a tool implementing a wrapper spoiling system, and discuss some practical spoiling techniques which are also experimentally tested

The task of an information integration system is to combine data residing at different sources, providing the user with a unified view of them, called global schema. Users formulate queries over the global schema, and the system suitably queries the sources, providing an answer to the user, who is not obliged to have any information about the sources. Recent developments in IT such as the expansion of the Internet and the World Wide Web, have made available to users a huge number of information sources, generally autonomous, heterogeneous and widely distributed: as a consequence, information integration has emerged as a crucial issue in many application domains, e.g., distributed databases, cooperative information systems, data warehousing, or on-demand computing. Recent estimates view information integration to be a $10 Billion market by 2006 [14].

Metaquerying is a data mining technology by which hidden dependencies among several database relations can be discovered. This tool has already been successfully applied to several real-world applications, but only preliminary results about the complexity of metaquerying can be found in the literature. In this article, we define several variants of metaquerying that encompass, as far as we know, all the variants that have been defined in the literature. We study both the combined complexity and the data complexity of these variants. We show that under the combined complexity measure metaquerying is generally intractable (unless P = NP ), lying sometimes quite high in the complexity hierarchies (as high as NP PP ), depending on the characteristics of the plausibility index. Nevertheless, we are able to single out some tractable and interesting metaquerying cases, whose combined complexity is LOGCFL-complete. As for the data complexity of metaquerying, we prove that, in general, it is within TC 0 , but lies within AC 0 in some simpler cases. Finally, we discuss the implementation of metaqueries by providing algorithms that answer them.

Metaquerying is a datamining technology by which hidden dependencies among several database relations can be discovered. This tool has already been successfully applied to several real-world applications. Recent papers provide only very preliminary results about the complexity of metaquerying. In this paper we define several variants of metaquerying that encompass, as far as we know, all variants defined in the literature. We study both the combined complexity and the data complexity of these variants. We show that, under the combined complexity measure, metaquerying is generally intractable (unless P=NP), but we are able to single out some tractable interesting metaquerying cases (whose combined complexity is LOGCFL-complete). As for the data complexity of metaquerying, we prove that, in general, this is in P, but lies within AC0 in some interesting cases. Finally, we discuss the issue of equivalence between metaqueries, which is useful for optimization purposes.