Second International Compulog/ALP Summer School
in
Computational Logic
(A Report)

Islam Elkabani, Omar Elkhatib, Hung Le

Department of Computer Science - New Mexico State University

Editor: Enrico Pontelli

The PDF-version of this article can be found here.

INTRODUCTION
The second international summer school in Constraint and Logic Programming has been held on the campus of University of Texas at Dallas, TX. The summer school is meant for students, researchers, and programmers interested in constraints, logic programming, computational logic and its applications.
The 2nd summer school on computational logic builds on the highly successful 1st summer school in (C)LP held in Las Cruces, NM, in 1999.

The lectures have been provided by internationally renowned researchers who have made significant contributions to research. The summer school was especially directed to Ph.D. students who are just about to start research.

The summer school consisted of half day tutorials on the following topics:

• Constraint Logic Programming and its Applications by Pascal van Hentenryck (Brown University)
• The Semantic Web and Computational Logic by Stefan Decker (Digital Enterprise Research Institute, Ireland)
• Answer Set Programming by Chitta Baral (Arizona State University)
• Tabled Logic Programming and its Applications by David S. Warren (SUNY Stony Brook)
• Logical Aspects of Computer Security by Ninghui Li (Purdue University)
• Inductive Logic Programming and its Applications by Vitor Santos Costa (University of Wisconsin and UFRJ Brazil)
  

Several scholarships have been made  available to the participants. About 70 students attended the summer school.


CONSTRAINT PROGRAMMING
The lectures on Constraint Programming and its Applications havebeen offered by Pascal van Hentenryck (Brown University).
The first lecture on Constraint Programming took place on the first day of the Summer School (June 14), from 1:00 to 3:30.

The first class focused on the more general concepts of Constraint Programming and Constraint Logic Programming. Dr. van Hentenryck provided an overview of the field of constraint programming, illustrating the main difficulties encountered when dealing with constraint resolution. Through a number of clear examples, the instructor provided an overview of key concepts, highlighting the differences between constraint programming and more traditional search---e.g., by viewing constraint programming as a combination of branch, prune, and bound.

During the first lecture, Dr. van Hentenryck described a number of algorithms for handling some of the global constraints, such as
alldifferent and card. Furthermore, he presented the discrepancy search, which is an incomplete search algorithm that performs the following:

• Assume a good heuristic.
• Trust the heuristic less over.
• May avoid being stuck in suboptimal region.
  

The second lecture on Constraint Programming took place on the  second day (Jun. 15) from 9:00 to 11:30. During this lecture, Dr. van Hentenryck presented a significant number of application problems that are NP-complete, but can be effectively handled using finite domain constraint solvers. Some of the problems presented are:

• Euler knight: where a knight is required to visit all the positions in the chess-board exactly once.
• Car sequencing: where we need to meet the customers' requirements in assemblying a car (leather seat, sun roof, etc.).
• Scene allocation: this is the problem of producing a movie at minimal cost by deciding when to shoot scenes. Constraints on number of actors, fees and number of scenes per day have to be satisfied.
• Sport scheduling: where n-teams are scheduled to play with each others. Constraints that need to be satisfied include: only two teams are scheduled to play at any time, the period is limited and the number of play for each period is specified.
  

LOGICAL ASPECTS OF COMPUTER SECURITY

The lectures on Logical Aspects of Computer Security have been offered by Dr. Ninghui Li from Purdue University.

The first lecture took place on June 16, from 4:00 to 6:30. During the first lecture, Dr. Li provided:

• A comprehensive introduction to the fundamental issues of Access Control.
• A brief introduction to Trust Management.
• A discussion of a logic-based semantics for Simple Distributed Security Infrastructure (SDSI).
• A distributed deduction system for Role-based Truth-management languages (RT₀).
  

The second lecture took place on June 17 from 1:00 to 3:30. During this lecture, Dr. Li offered an in-depth of security analysis for
the RT₀ languages. He continued by describing how Constraint Datalog can be used as a semantic foundation for trust-management languages. He concluded his presentation by discussing some open problems in the area of trust-management as well as other possible applications of logic programming in the field of access control.

THE SEMANTIC WEB AND COMPUTATIONAL LOGIC

The lectures on Computational Logic and the Semantic Web have been offered by Dr. Stefan Decker, from the Digital Enterprise Research Institute, Ireland.

The first lecture took place on the first day of the Summer School (June 14) from 9:00 to 11:30. During the first lecture, Dr. Decker provided an overview of what the Semantic Web is, an what are the basic motivations that brought it into existence. Dr. Decker proceeded with an analysis of the information aspects and basic components of the Semantic Web, including a nice discussion of metadata and the Resource Description Framework (RDF).

The second lecture took place on June 15, from 4:00 to 6:30. Dr. Decker  continued his overview of the Semantic Web, focusing in particular on Ontologies. Dr. Decker introduced different formalisms for dealing with ontologies, including Description Logics, the Web Ontology Language (OWL), Description Logic Programming, and F-logic. The discussion proceeded towards applications of logic programming in reasoning about ontologies and current extensions of ontology languages. The lecture closed with a brief picture of the future of the Semantic Web.

TABLED LOGIC PROGRAMMING

The lectures on Tabling in Logic Programming have  been offered by Dr. David S. Warren, from SUNY Stony Brook.

The first lecture took place on June 16, from 9:00 to 11:30. In this lecture, Dr. Warren introduced the problem of non-termination in traditional Prolog systems, through some fundamental examples - such as symmetric and transitive relations.
Dr. Warren continued by showing how these problems can be effectively dealt with using tabled logic programming, and its implementation in the XSB system. The discussion highlighted how tabling can eliminated redundant computation, by storing in a table goals and their previously computed answers. In particular, all programs that do not use structures have been shown to terminate under tabled evaluation.

The second lecture on tabling took place on June 17th, from 4:00 to 6:30. In this lecture, Dr. Warren discussed the following topics:

• Applications of tabled logic programming in Databases, Grammars, Automata Theory and Dynamic Programming.
• A general evaluation strategy for recursive definitions using tabling.
• Program processing using tabling.
• Beyond simple tabling (Negation, Aggregation and Constraints).
  

ANSWER SET PROGRAMMING

The lectures on Answer Set Programming have been offered by Dr. Chitta Baral, from Arizona State University.

In the first lecture, Dr. Baral presented the foundations of Knowledge Representation and Reasoning (KRR), and he offered a perspective of how Answer Set Programming - and more specifically its instantiation in the AnsProlog system - can provide a very
effective solution to the key problems of KRR. In his lecture, Dr. Baral presented terminologies, syntax and semantics of AnsProlog. A rich collection of examples have been discussed to introduce AnsProlog, along with a discussion of basic techniques for declarative problem solving using AnsProlog.

During the second lecture, Dr. Baral concentrated on one of the main application of AnsProlog: reasoning about action and planning  Starting from a simple example and its solutions, Dr. Baral led the students to different and more complex problems and how they could be solved effectively using AnsProlog. In the last part, he provided an overview of the current implementations of  systems that can be used to compute answer sets - such as Smodels, DLV, and ASSAT. Dr. Baral closed the lecture with a discussion of the complexity and expressiveness of the AnsProlog* subclass.

INDUCTIVE LOGIC PROGRAMMING

The lectures on Inductive Logic Programming have been offered by Dr. Vitor Santos Costa, from the Federal University of Rio de Janeiro (currently at the University of Wisconsin).

During the first lecture, Dr. Santos Costa gave an overview of the different fields of machine learning and concentrated on Inductive Logic Programming. The presentation of the basic techniques in Inductive Logic Programming developed around the use of the Aleph system and its application to solve Michalski's train problem.
Dr. Santos Costa showed how the system can be used to tackle this example, and some specific techniques that have been applied in the implementation of Aleph. The discussion continued with a description of the structure of the search space in inductive logic programming and how its efficient exploration is tackled in the existing systems.
The lecture closed with the analysis of the issues of correctness and with the presentation of another system, FOIL, to discuss other inductive logic programming techniques.

During the second lecture, Dr. Santos Costa started with the principles of Inductive Logic Programming. The techniques introduced in the first lecture have been revisited in detail and in the context of both top-down and bottom-up approaches. Dr. Santos Costa introduced the principles of least generalization and refinement, and their use in some popular systems (e.g., GOLEM).
Dr. Santos Costa closed his presentation with some examples of applications of inductive logic programming,  and with an overview  of the main current research efforts in this field.