ICLP on Monday, July 19th

09:00‑10:00 ICLP Invited talk
Chair: Manuel Hermenegildo
Location: AT LT3
09:00 Molham Aref (LogicBlox)
Datalog for Enterprise Software: from Industrial Applications to Research.
10:30‑12:30 Applications
Chair: Thom Fruehwirth
Location: AT LT3
10:30 Michela Milano, Marco Gavanelli, Fabrizio Riguzzi and Paolo Cagnoli
Logic-Based Decision Support for Strategic Environmental Assessment

Strategic Environmental Assessment is a procedure aimed at introducing systematic assessment of the environmental effects of plans and programs. This procedure is based on the so called coaxial matrices that define dependencies between plan activities (infrastructures, plants, resource extractions, buildings, etc.) and positive and negative environmental impacts, and dependencies between these impacts and environmental receptors. Up to now, this procedure is manually implemented by environmental experts for checking the environmental effects of a given plan or program, but it is never applied during the plan/program construction. A decision support system, based on a clear logic semantics, would be an invaluable tool not only in assessing a single, already defined plan, but also during the planning process in order to produce an optimized, environmentally assessed plan and to study possible alternative scenarios. We propose two logic-based approaches to the problem, one based on Constraint Logic Programming and one on Probabilistic Logic Programming that could be, in the future, conveniently merged to exploit the advantages of both. We test the proposed approaches on a real energy plan and we discuss their limitations and advantages.

11:00 Miguel Gomez-Zamalloa, Elvira Albert and German Puebla
Test Case Generation for Object-Oriented Imperative Languages in CLP

Testing is a vital part of the software development process. Test Case Generation (TCG) is the process of automatically generating a collection of test cases which are applied to a system under test. White-box TCG is usually performed by means of symbolic execution, i.e., instead of executing the program on normal values (e.g., numbers), the program is executed on symbolic values representing arbitrary values. When dealing with an object-oriented (OO) imperative language, symbolic execution becomes challenging as, among other things, it must be able to backtrack, complex heap-allocated data structures should be created during the TCG process and features like inheritance, virtual invocations and exceptions have to be taken into account. Due to its inherent symbolic execution mechanism, we pursue in this paper that Constraint Logic Programming (CLP) has a promising unexploited application field in TCG. We will support our claim by developing a fully CLP-based framework to TCG of an OO imperative language, and by assessing it on a corresponding implementation on a set of challenging Java programs. A unique characteristic of our approach is that it handles all language features using only CLP and without the need of developing specific constraint operators (e.g., to model the heap).

11:30 Gregory Gelfond, Chitta Baral, Enrico Pontelli and Tran Son
Using Logic Programming for Finding Models in the Logics of Knowledge and its Applications

The logics of knowledge are modal logics that have been shown to be effective in representing and reasoning about knowledge in multi-agent domains. Yet, to date very few computational frameworks for dealing with computation of models and useful transformations in logics of knowledge (e.g., to support multi-agent planning with knowledge actions and degrees of visibility) have been proposed. This paper explores the use of logic programming to encode interesting forms of logics of knowledge and compute Kripke models. The logic programming modeling is expanded with useful operators on Kripke structures, adequate to support multi-agent planning in presence of both world-altering and knowledge actions. This results in the first ever implementation of a planner for such type of complex multi-agent domains.

12:00 Nuno P. Lopes, Juan Navarro Perez, Andrey Rybalchenko and Atul Singh
Applying Prolog to Develop Distributed Systems

Development of distributed systems is a difficult task. Declarative programming techniques hold a promising potential for effectively supporting programmer in this challenge. While Datalog-based languages have been actively explored for programming distributed systems, Prolog received relatively little attention in this application area so far. In this paper, we investigate the applicability of a Prolog-based programming system, called DAHL, for the declarative development of distributed systems. For this task, we extend Prolog with an event-driven control mechanism and built-in networking procedures. Our experimental evaluation using a distributed hashtable data structure, a protocol for achieving Byzantine fault tolerance, and a distributed software model checker -- all implemented in DAHL -- indicates the viability of the approach.

14:00‑15:00 Technical Communications - IV
Chair: Tomi Janhunen
Location: AT LT3
14:00 Paulo Shakarian, V.S. Subrahmanian and Maria Luisa Sapino
Using Generalized Annotated Programs to Solve Social Network Optimization Problems

Reasoning about social networks (labeled, directed, weighted graphs) is now becoming increasingly important and there are now models of how certain phenomena (e.g. adoption of products/services by consumers, spread of a given disease) ``diffuse'' through the network. Some of these diffusion models can be expressed via generalized annotated programs (GAPs). In this paper, we consider the following problem: suppose we have a given goal to achieve (e.g. maximize the expected number of adoptees of a product or minimize the spread of a disease) and suppose we have limited resources to use in trying to achieve the goal (e.g. give out a few free plans, provide medication to key people in the SN) - how should these resources be used so that we optimize a given objective function related to the goal? We define a class of social network optimization problems}(SNOPs) that supports this type of reasoning. We formalize and study the complexity of SNOPs, provide algorithms to solve SNOPs, and show how they can be used in conjunction with existing economic and disease diffusion models.

14:12 Fabrizio Riguzzi and Terrance Swift
Tabling and Answer Subsumption for Reasoning on Logic Programs with Annotated Disjunctions

Probabilistic Logic Programming is an active field of research, with many proposals for languages, semantics and reasoning algorihms. One such proposal, Logic Programming with Annotated Disjunctions (LPADs) represents probabilistic information in Logic Programming in a sound and simple way. This paper presents two contributions to the evaluation of LPADs. The first is the definition of a semantics for LPADs with function symbols, which is needed for many domains (including some standard benchmarks used in this paper). The second is the algorithm Probabilistic Inference with Tabling and Answer subsumption (PITA) for computing the probability of queries. Answer subsumption is a feature of tabling that allows the combination of different answers for the same subgoal in the case in which a partial order can be defined over the answers. We have applied it in our case since probabilistic explanations (stored as BDDs in PITA) posses a natural lattice structure. PITA has been implemented in XSB and compared with the ProbLog, cplint and CVE systems. The results show that in almost all cases, PITA is able to solve larger problems than competing algorithms and is usually faster.

14:24 Domenico Corapi, Alessandra Russo and Emil Lupu
Inductive Logic Programming as Abductive Search

We present a novel approach to non-monotonic ILP and its implementation called TAL (Top-directed Abductive Learning). TAL overcomes some of the completeness problems of ILP systems based on Inverse Entailment and is the only top-down ILP system that allows background theories and hypotheses to be normal logic programs. The approach relies on mapping an ILP problem into an equivalent ALP one. This enables the use of established ALP proof procedures and the specification of richer language bias with integrity constraints. The mapping provides a principled search space for an ILP problem, over which an abductive search is used to compute inductive solutions. Different search strategies and heuristics can be employed, thus providing a general learning framework in which both completeness and efficiency can be simultaneously achieved.

14:36 Marco Alberti, Marco Gavanelli and Evelina Lamma
Runtime Addition of Integrity Constraints in Abductive Logic Programs

Abductive Logic Programming (ALP) is a computationally founded representation of abductive reasoning. In most ALP frameworks, integrity constraints express domain-specific logical relationships that abductive answers are required to satisfy.

Integrity constraints are usually known a priori. However, in some applications (such as interactive abductive logic programming, multi-agent interactions, contracting) it makes sense to relax this assumption, in order to let abductive reasoning start with incomplete knowledge of integrity constraints, and to continue without restarting when new integrity constraints become known.

In this paper, we propose a declarative semantics for a general abductive logic programming framework which allows addition of integrity constraints during the abductive reasoning process.

We propose an operational instantiation and an implementation of such a framework based on the SCIFF language and proof procedure.

14:48 Gerardo Simari and V.S. Subrahmanian
Abductive Inference in Probabilistic Logic Programs

Action-probabilistic logic programs (APLPs) are a class of probabilistic logic programs that have been extensively used during the last few years for modeling behaviors of entities. Rules in APLPs have the form "If the environment in which entity E operates satisfies certain conditions, then the probability that E will take some action A is between L and U". Given an APLP, we are interested in trying to change the environment, subject to some constraints, so that the probability that entity E takes some action (or combination of actions) is maximized. This is called the Basic Probabilistic Logic Abduction Problem (Basic PLAP). We first formally define and study the complexity of Basic PLAP and several variants of it. We then provide an exact (exponential) algorithm to solve Basic PLAP, followed by more efficient algorithms for specific subclasses of Basic PLAP. We also develop appropriate heuristics to solve Basic PLAP efficiently.

15:30‑17:30 Applications and Systems
Chair: Neng-Fa Zhou
Location: AT LT3
15:30 Alessandro Dal Palu, Agostino Dovier, Federico Fogolari and Enrico Pontelli
CLP-based protein fragment assembly

The paper investigates a novel approach, based on Constraint Logic Programming (CLP), to predict the 3D conformation of a protein via fragments assembly. The fragments are extracted by a preprocessor from a database of known protein structures---also developed for this work--- that clusters and classifies the fragments according to similarity and frequency. The problem of assembling fragments into a complete conformation is mapped to a constraint solving problem and solved using CLP. The constraint-based model uses a medium discretization degree $\calpha$-centroid protein model that offers good efficiency and a good approximation for space filling. The approach also makes use of an ad-hoc energy function developed specifically for this work, and applies a large neighboring search strategy. The preliminary results support the correctness and efficiency of the method. The declarative nature of the solution is suitable to future extensions, e.g.. different size fragments for better accuracy.

16:00 Marcello Balduccini and Sara Girotto
Formalization of Psychological Knowledge in Answer Set Programming and its Application

In this paper we explore the use of Answer Set Programming (ASP) to formalize, and reason about, psychological knowledge. In the field of psychology, a considerable amount of knowledge is still expressed using only natural language. This lack of a formalization complicates accurate studies, comparisons, and verification of theories. We believe that ASP, a knowledge representation formalism allowing for concise and simple representation of defaults, uncertainty, and evolving domains, can be used successfully for the formalization of psychological knowledge. To demonstrate the viability of ASP for this task, in this paper we develop an ASP-based formalization of the mechanics of Short-Term Memory. We also show that our approach can have rather immediate practical uses by demonstrating an application of our formalization to the task of predicting a user's interaction with a graphical interface.

16:30 Robert Brummayer and Matti Järvisalo
Testing and Debugging Techniques for Answer Set Solver Development

This paper develops automated testing and debugging techniques for answer set solver development. We describe a flexible grammar-based black-box ASP fuzz testing tool which is able to reveal various defects such as unsound and incomplete behavior, i.e. invalid answer sets and inability to find existing solutions, in state-of-the-art answer set solver implementations. Moreover, we develop delta debugging techniques for shrinking failure-inducing inputs on which solvers exhibit defective behavior. Namely, we develop a generic delta debugging algorithm for ASP, and evaluate two different implemented elimination strategies for the algorithm.

17:00 Johannes Oetsch, Joerg Puehrer, Martin Schwengerer and Hans Tompits
The System Kato: Detecting Cases of Plagiarism for Answer-Set Programs

We present the tool Kato which is, to the best of our knowledge, the first tool for plagiarism detection that is directly tailored for answer-set programming (ASP). Kato aims at finding similarities between (segments of) logic programs to help detecting cases of plagiarism. Currently, the tool is realised for DLV programs but it is designed to handle various logic-programming syntax versions. We introduce the theoretical underpinning of the tool, review its basic features, and present an evaluation of our approach for plagiarism detection on program collections that stem from different courses at our university.