ICLP on Sunday, August 20th

Session 9: Applications II (09:00‑10:00)
Chair: Veronica Dahl
Location: Grand Ballroom A

09:00‑09:30

Chitta Baral (Arizona State University) Saadat Anwar (ASU) Juraj Dzifcak (ASU) Hiro Takahashi (ASU) Macros, macro calls and use of ensembles in modular Answer Set Programming Currently, most knowledge representation using logic programming with answer set semantics (AnsProlog) is `flat'. In this paper we elaborate on our thoughts about a modular structure for knowledge representation and declarative problem solving formalism using AnsProlog. We present language constructs that allow defining of modules and calling of such modules from programs. This allows one to write large knowledge bases or declarative problem solving programs by reusing existing modules instead of writing everything from scratch. Our ultimate aim is to facilitate the creation and use of a repository of modules that can be used by knowledge engineers without having to re-implement basic knowledge representation concepts from scratch.

09:30‑10:00

C.R. Ramakrishnan (SUNY, Stony Brook) IV Ramakrishnan (SUNY Stony Brook) David Warren (Dept of Computer Science, SUNY Stony Brook) Deductive Spreadsheets using Tabled Logic Programming Rule-based specifications in Datalog are used in a number of application areas, such as configuration management, access control and trust management, decision making, etc. However, rules sets are typically hard to maintain; the rules often interact in subtle ways, making them difficult to understand and reason about. This has impeded the wide-spread adoption of rule-based computing. This paper describes the design and implementation of XcelLog, a deductive spreadsheet system (DSS), that permits users to specify and maintain Datalog rules using a familiar spreadsheet interface. The driving idea underlying the system is to treat sets as the fundamental data type and rules as specifying relationships among sets, and use the spreadsheet metaphor to create and view the materialized sets. The fundamental feature that makes XcelLog suitable for non-programmers is that the user mainly sees the effect of the rules; when rules or basic facts change, the user sees the impact of the change immediately. This enables the user to gain confidence in the rules and their modification, and also experiment with what-if scenarios without any programming. XcelLog is implemented as an add-in to Excel with XSB serving as the rule engine for evaluating Datalog specifications. Preliminary experience with using XcelLog indicates that it is indeed feasible to combine the power of rule-based computing and the elegance and simplicity of the spreadsheet metaphor, so that end users can encode and maintain rule bases with little or no programming.

Break (10:00‑10:30)

Session 10: Applications II (cont'd) (10:30‑11:00)
Chair: Veronica Dahl
Location: Grand Ballroom A

10:30‑11:00

Luis Quintano (Universidade de Évora - Portugal) Irene Rodrigues (Universidade de Évora - Portugal) Using a Logic Programming framework to Control Database Query Dialogues in Natural Language We present a natural language question/answering system to interface the University of Évora databases that uses clarification dialogs in order to clarify user questions. It was developed in an integrated logic programming framework, based on constraint logic programming using the GnuProlog(-cx) language and the ISCO framework. The use of this LP framework allows the integration of Prolog-like inference mechanisms with classes and inheritance, constraint solving algorithms and provides the connection with relational databases, such as PostgreSQL. This system focus on the questions' pragmatic analysis - to handle ambiguity, Proper Nouns resolution and the pp-attachment problem - and on an efficient dialogue mechanism - which is able to place relevant questions to clarify the user intentions in a straightforward manner. This paper briefly presents this innovative system focusing on its ability to correctly determine the user intention through its dialogue capability.

Session 11: Poster Presentations (11:00‑12:30)
Chair: Agostino Dovier
Location: Grand Ballroom A

11:00‑11:05	Rafael Caballero (Universidad Complutense de Madrid) Mario Rodriguez Artalejo (Universidad Complutense de Madrid) Rafael del Vado Virseda (Universidad Complutense de Madrid) Declarative Diagnosis of Wrong Answers in Constraint Functional-Logic Programming We present a declarative method for diagnosing wrong computed answers in CFLP(D), a newly proposed generic scheme for lazy Constraint Functional-Logic Programming which can be instantiated by any constraint domain D given as parameter, and supports a powerful combination of functional and constraint logic programming over D. Our approach extends and combines declarative debugging techniques previously developed for less expressive programming paradigms, namely the CLP(D) scheme and lazy functional logic languages. Debugging starts with the observation of a wrong computed answer which the user regards as incorrect w.r.t. an intended model that provides a declarative description of the program's semantics. Debugging proceeds by exploring an abridged proof tree that provides a purely declarative view of the computation, so that the user does not need to understand the complex underlying operational mechanism. Debugging ends with the detection of a function rule in the program that is incorrect w.r.t. the intended model. We prove the logical correctness of the debugging method for any sound CFLP(D)-system whose computed answers are logical consequences of the program, and we describe a practical tool which implements the debugging method for the domain of arithmetic constraints over the real numbers.
11:05‑11:10	Thi-Bich-Hanh Dao (Universite d'Orleans) Khalil Djelloul (Universite Aix-Marseille II) Solving First-Order Constraints in the Theory of the Evaluated Trees We present in this paper a general algorithm for solving first-order constraints in the theory $T$ of the evaluated trees which is a combination of the theory of finite or infinite trees and the theory of the rational numbers with addition and subtraction and a linear dense order relation. The algorithm is given in the form of 28 rewriting rules. It transforms a first-order formula $\varphi$ - which can possibly contain free variables - into a disjunction $\phi$ of solved formulas which is equivalent in $T$, without new free variables and such that $\phi$ is either the formula $\vrai$ or the formula $\faux$ or a formula having at least one free variable and being equivalent neither to $\vrai$ nor to $\faux$ in $T$. In particular if $\varphi$ does not contain free variables then $\phi$ is either the formula $\vrai$ or $\faux$. If $\phi$ has free variables then the solutions on free variables are expressed in an explicit way and $\phi$ can be directly transformed into a boolean combination of quantified conjunctions of atomic formulas which do not accept elimination of quantifiers. The correctness of our algorithm is another proof of the completeness of this theory.
11:10‑11:15	Hai-Feng Guo (University of Nebraska at Omaha) Miao Liu (University of Nebraska at Omaha) Bharat Jayaraman (State University of New York at Buffalo) Relaxation on Optimization Predicates Traditional constraint logic programming (CLP) specifies an optimization problem by using a set of constraints and an objective function. In many applications, optimal solutions may be difficult or impossible to obtain, and hence we are interested in finding suboptimal solutions, by either relaxing the constraints or the objective function. In this paper, we focus on the relaxation problem in preference logic programming (PLP), where an optimization predicate is specified in a declarative way by separating its general definition from its solution preferences. Relaxation on optimization predicates in PLP can be achieved in two different approaches, by either relaxing the constraints or relaxing the objective function such as a query to an optimization predicate. Both approaches can be properly expressed in the framework of PLP.
11:15‑11:20	Ricardo Rocha (DCC-FC & LIACC, University of Porto) Handling Incomplete and Complete Tables in Tabled Logic Programs Most of the recent proposals in tabling technology were designed as a means to improve some practical deficiencies of current tabling execution models. The discussion we address in this paper was also motivated by practical deficiencies we encountered, in particular, when dealing with incomplete and complete tables. Incomplete tables became a problem when, as a result of a pruning operation, the computational state of a tabled subgoal is removed from the execution stacks before being completed. On the other hand, complete tables became a problem when the system runs out of memory. To handle incomplete tables, we propose an approach that avoids re-computation when the already stored answers are enough to evaluate a repeated call. To handle complete tables, we propose a memory management strategy that automatically recovers space from the tables when the system runs out of memory. To validate our proposals, we have implemented them in the YapTab tabling system as an elegant extension of the original design.
11:20‑11:25	Cláudio Silva (DCC-FC & LIACC, University of Porto) Ricardo Rocha (DCC-FC & LIACC, University of Porto) Ricardo Lopes (DCC-FC & LIACC, University of Porto) An External Module For Implementing Linear Tabling in Prolog In previous work, we have presented a proposal to combine the power of tabling with the Extended Andorra Model (EAM) and we have proposed the ability to use an external module for implementing tabling primitives that provide direct control over the search strategy. Currently, we have already a preliminary implementation of two linear tabling approaches, the SLDT and the DRA mechanisms, in our external module. Preliminaries results, on a set of common benchmarks for tabled execution, allows us to make a first and fair comparison between the SLDT and the DRA mechanisms and, therefore, better understand the advantages and weaknesses of each. Starting from these results, we are now working on a new proposal that tries to combine the best features of both in order to produce a more robust and efficient linear tabling mechanism to experiment with the EAM.
11:25‑11:30	Edison Mera (Technical University of Madrid) Pedro Lopez-Garcia (Universidad Politécnica de Madrid) German Puebla (Technical University of Madrid) Manuel Carro (Technical University of madrid) Manuel Hermenegildo (T.U. Madrid (UPM) and U. of New Mexico (UNM)) Using Combined Static Analysis and Profiling for Logic Program Execution Time Estimation Effective static analyses have been proposed which allow inferring bounds in terms of number of resolutions or reductions. These have the advantage of being independent from the platform on which the programs are executed. Also, the bounds obtained with static analysis have been proved useful in a number of applications such as granularity control in parallel execution. On the other hand, in certain mobile/pervasive computation scenarios where different platforms come into play, with each platform having different capabilities, it is more interesting to express costs in metrics that include the characteristics of the platform. In particular, it is specially interesting to be able to determine upper and lower bounds on actual execution time. With this objective in mind, we propose a method which allows inferring upper and lower bounds on the execution times of procedures of a program in a given execution platform. The approach combines compile-time cost bounds analysis with a one-time profiling of the plaform in order to determine the values of certain constants. These constants calibrate a cost model which from them on is able to compute statically time bound functions for procedures and to predict with a significant degree of accuracy the execution times of such procedures. The approach has been implemented and integrated in the CiaoPP system.
11:30‑11:35	Quan Phan (DTAI group, Computer Science Dept., Katholieke Universiteit Leuven) Gerda Janssens (DTAI group, Computer Science Dept., Katholieke Universiteit Leuven) Towards Region-based Memory Management for Deterministic Mercury Programs (Extended Abstract) Region-based memory management is a form of compile-time memory management, well-known from the functional programming world. This paper describes region-based memory management for the Mercury language using a points-to graph that models regions and distributes values of program variables over regions. First, region analysis determines the different regions in the program. Second, the liveness of the regions is computed. Finally, a program transformation adds region annotations to the program for region support. Our approach obtains good results for deterministic programs, which is exactly the context in which memory can be recovered at compile-time. Our method can be extended with region instructions to support programs with modules. It seems to have the potential to integrate reuse as known from compile-time garbage collection within regions.
11:35‑11:40	Salvador Abreu (Universidade de Evora) Vitor Nogueira (Universidade de Évora) Towards Structured Contexts and Modules Contextual Logic Programming was proposed by Monteiro and Porto as a means of bringing modularity to the Prolog language. It was improved upon as a practical extension in a high performance Prolog system by Abreu and Diaz, providing a program structuring mechanism as well as fulfilling some of Prolog’s shortcomings when used for programming in-the-large, namely by enabling an object-oriented programming style without relinquishing the expressiveness and semantic robustness of Logic Programs. For their dynamically configurable structure, contexts clearly subsume the base mechanisms of most module systems, this being particularly true of the ISO/IEC Prolog Modules standard proposal. This strength is also a weakness: the dynamic nature of a context leads to difficulties in predicting their structure, at compile time, this is particularly true when taking a separate compilation approach. We address these issues by presenting an approach whereby contexts are restricted to statically predictable forms and illustrate the proposal by applying it to implement ISO modules.
11:40‑11:45	Vitor Nogueira (Universidade de Évora) Salvador Abreu (Universidade de Evora) TowardsTemporal Contextual Logic Programming Contextual Logic Programming (CxLP) is a simple and powerful language that extends logic programming with mechanisms for modularization. The importance of temporal representation and reasoning is well known not only in the database community but also in the artificial intelligence one. In this paper we propose a language called Temporal Contextual Logic Programming that can be regarded as a two-sorted sorted extension of CxLP. Besides giving a brief description of its operational semantics we also present a real-world application.
11:45‑11:50	Veronica Dahl (School of Computing Science, Simon Fraser University) Baohua Gu (School of Computing Science, Simon Fraser University) Semantic Property Grammars for Knowledge Extraction from Biomedical Text We present Semantic Property Grammars, designed to extract concepts and relations from biomedical texts. The implementation adapts a CHRG parser we designed for Property Grammars, which views linguistic constraints as properties between sets of categories and solves them by constraint satisfaction, can handle incomplete or erroneous text, and extract phrases of interest selectively. We endow it with concept and relation extraction abilities as well.
11:50‑11:55	Juan Fernández Ortiz (Technical University of Madrid) Jørgen Villadsen (Computer Science, Roskilde University) Natural Language Processing Using Lexical and Logical Combinators We describe a Prolog implementation of the sequent calculus for the type theory Nabla that can make syntactical and semantical analyses of a fragment of natural language using combinators.
11:55‑12:00	Dulce Aguilar-Solis (Simon Fraser University) Learning Semantic Parsers: a Constraint Handling Rule Approach Semantic parsing is the process of mapping a natural language input into some structure meaning representation. Even though this process is natural and smooth for human beings, it constitutes a huge problem in natural language processing. Semantic parsing is a challenging and interesting problem that has been severely understudied. The ultimate goal of this work is to develop a novel constraint handling rule (CHR) approach to learn semantic parsers for mapping natural language sentences to any kind of compositional formal representation. As first step, this work shows how to learn one new semantic rule without going through the process of leaning again the set of known semantic rules. The proposed approach uses CHR and assumptions to examine the actual state and the desired state of the semantic representation of a sentence. A series of actions will be inferred to transform the actual semantic representation to the final representation.
12:00‑12:05	Hugo Lopez (Universidad Javeriana - Cali) Catuscia Palamidessi (INRIA) Jorge A. Perez (Universidad Javeriana - Cali) Camilo Rueda (Universidad Javeriana - Cali) Frank D. Valencia (CNRS) A Declarative Framework for Security: Secure Concurrent Constraint Programming This poster describes our project Secure CCP (SCCP) which aims at advancing both the theory and tools of Concurrent Constraint Programming (CCP) for analyzing and programming security protocols. Our motivation arises from the strong resemblance between modern process calculi for Security and CCP, the great variety of reasoning techniques and tools for CCP, and positive experience with the ICLP'03 Workshop COLOPS (Constraint and Logic Programming in Security) coordinated by the the fifth author. The main goal of our project is to develop a CCP-based framework for security protocols. The novelty is the combination in one unique formalism of behavioral and logical techniques. The expected outcome is two-fold. On one hand, we will advance the CCP theory to deal with new challenging concepts from Security. On the other hand, we will produce a specification language and tools to model and automatically verify security protocols.
12:05‑12:10	Andrei Mantsivoda (Irkutsk State University) Anton Malykh (Irkutsk State University) Vladimir Lipovchenko (Irkutsk State University) Logic programming in Knowledge Domains We propose an approach to combining logic programming and knowledge representation paradigms. This approach is based on the conception of description terms. LP and KR are integrated in such a way that their underlying logics are carefully separated. A core idea here is to push the KR techniques on the functional level. On the LP level the knowledge base is considered as a constraint store, in which special propagation methods are ruling. A NCC calculus that handles description terms is developed as an underlying inference system for propagation. On the basis of this formalism, a constraint logic programming language integrating both LP and KR approaches is designed.
12:10‑12:15	Paulo Jorge Lopes de Moura (University of Beira Interior, Portugal) Vincent Marchetti (KShell Analysis) Logtalk processing of STEP Part 21 files STEP is an international standard for modeling information used in manufacturing activities; Part 21 is a STEP component that standardizes the exchange of this information through text files. We are working on applying logic programming techniques to processing STEP data models. The STEP standard specifies the entities, attributes, consistency rules, and functions used for describing and validating manufacturing information. Most STEP entities and data types are organized into hierarchies, making an object-oriented approach the most straight-forward implementation solution. Our work uses Logtalk, an object oriented extension to Prolog, as the primary implementation tool.
12:15‑12:20	Edna Ruckhaus (Universidad Simon Bolivar, Dept. Computer Science) Vladimir Kolovski (University of Maryland - College Park) Bijan Parsia (University of Maryland, College Park) Bernardo Cuenca-Grau (University of Manchester) Integrating Datalog with OWL: Exploring the AL-log Approach The need for integrating the Description Logics (DL) and the Datalog paradigms has been the focus of several research initiatives. Among them the hybrid knowledge representation system AL-log (Donini et al.,1998), which combines the DL language ALC with positive Datalog. One advantage of this system is that one can couple a Datalog reasoner and an ALC reasoner in a very lightweight way. In AL-log, the interaction between the two components is obtained by allowing constraints in the clauses consisting of class DL atoms which ”type” variables or constants appearing elsewhere in the clause. So, not only is the implementation the result of a light coupling, but DL knowledge bases and rule sets can be developed relatively independently and then combined later. In the context of Semantic Web applications, there is an advantage in having the expressivity and reasoning capabilities of the combined formalisms. In this paper we present OWL-log, which is an implementation of an AL-log system where the DL component is extended to the Web Ontology Language OWL DL. We implemented an OWL-log reasoner coupled to the OWL reasoner Pellet and explored different query-answering strategies. We conducted an experimental study using a modified version of the LUBM benchmark in order to evaluate and compare the efficiency of the strategies. Also, to validate OWL-log’s usefulness we developed a prototype based on the Web ontology browsing and editing tool Swoop, and provided a use case on Web policy languages.
12:20‑12:25	Kazunori Ueda (Waseda University) Norio Kato (AIST Research Center for Verification and Semantics) Koji Hara (Waseda University) Ken Mizuno (Waseda University) LMNtal as a Unifying Declarative Language LMNtal (pronounced "elemental") is a simple language model based on hierarchical graph rewriting that uses assignment-free logical variables to represent connectivity and membranes to represent hierarchy. The major goal of LMNtal has been to unify various computational models addressing concurrency or multiset rewriting. LMNtal can be regarded as a constructor-free linear concurrent constraint language, and at the same time it can be regarded as a multiset rewriting language augmented with logical links and membranes that allow nesting and mobility. Another important goal of LMNtal has been to put hierarchical graph rewriting in the logical setting into practice and demonstrate its versatility, and the purpose of this paper is introduce LMNtal as a full-fledged, monolithic programming language, focusing on its design and practical aspects. Our LMNtal system, available on the net, smoothly integrates important features such as arithmetics, foreign-language interface, and modularity into the hierarchical graph rewriting model. Program examples are taken from diverse areas including functional programming, logic programming, process calculi, and multiset rewriting, to see how they relate to LMNtal.

Lunch break (12:30‑14:00)

Poster Session (14:00‑15:30)
Location: Aspen

Break (15:30‑16:00)