JICSLP'98 1998 Joint International Conference and Symposium on Logic Programming 15-19 June 1998 Manchester, UK

Keynote Talk

The pi calculus [2,3] was defined by Milner, Parrow and Walker as a "Calculus of Mobile Processes", extending work by Engberg and Nielsen [1]. It provides an underlying formal model for interactive systems which can change their configuration on the fly; this spans a large spectrum from mobile telephone networks to Java-like languages. The calculus aims to be a model for interactive behaviour as basic as is the lambda calculus for sequential computation. In fact, the lambda calculus can be modelled straightforwardly within it, and thus sequential computation can be seen as a special case of interaction.

The pi calculus is very simple; in my talk I shall presume no previous knowledge of it, but I shall not need to spend long in describing its primitive constructions. I shall focus on how it can be applied; in particular, how it admits a pleasant type system in which "type" can be understood to mean "pattern of interaction". In particular, I shall show how properties like "each mobile agent (ambulance? ..) will never be connected to more than one transmitter station at a time" are statically checkable types.

If time allows, I shall briefly discuss the language PICT (for distributed interactive systems) based upon pi calculus by Pierce and Turner [4], and the application of pi calculus to model authentication protocols by Abadi and Gordon [5].

References

1. Engberg, U. and Nielsen, M., A calculus of communicating systems with label-passing. Report DAIMI PB-208, Computer Science Department, University of Aarhus, Denmark, 1986.
2. Milner, R., Parrow, J. and Walker, D., A calculus of mobile processes, Parts I and II. Information and Computation, 100, 1, 1992, pp1-77.
3. Milner , R., The polyadic pi-calculus: a tutorial. In: Logic and Algebra of Specification, ed. F.L. Bauer, W. Brauer and H. Schwichtenberg, Springer Verlag, 1993, pp203-246.
4. Pierce, B. and Turner, D., Pict: a programming language based on the pi calculus. Technical Report, Computer Science Department, Indiana University, USA, 1997.
5. Abadi, M. and Gordon, A., A calculus for cryptographic protocols: the spi calculus. Technical Report 414, Computer Laboratory, University of Cambridge, UK, 1997.

Invited Talks

Inductive logic programming (ILP) is concerned with the induction of logic programs from examples and background knowledge. In ILP, the shift of attention from program synthesis to knowledge discovery resulted in advanced techniques that are practically applicable for discovering knowledge in relational databases. This paper gives a brief introduction to ILP and presents selected ILP techniques for relational knowledge discovery.

There are two basic themes in constraint logic programming (CLP). One is discrete or finite domain constraint programming based on the constraint satisfaction model (CSP). The other is continuous constraint programming based on linear programming (LP) and its extensions such as integer programming (IP). LP and IP are the mainstays of operations research (OR) and constitute a spectacularly successful set of implementations of deep mathematical algorithms. In this talk, we will discuss a family of problems known as disjunctive linear programs (DLPs) and consider how these applications are candidates for a combined attack.

The precise definition of DLP is as follows: In Rⁿ, half-spaces and hyperplanes are defined by linear constraints. An intersection of half-spaces in Rⁿ is called a polyhedral set. A disjunctive set is a finite union of polyhedral sets. A DLP is the problem of determining whether the intersection of a family of disjunctive sets is nonempty. This is the decision problem formulation. It is NP-Complete. (There is an obvious formal similarity with SAT.) The optimization problem with linear objective function is both NP-Hard and co-NP-Hard.

Interestingly, the DLP problem class, which constitutes an extension of IP, leads one to try to generalize many classical theorems of OR. This serves to pinpoint the distinction in IP between the role of integers as discrete points and their role as 0-1 Booleans. Some open and some solved problems in this area will be presented.

Addressing DLP applications requires an elegant collaboration among constraint-solving engines. Although this is not a new theme in CLP, going back as it does to work on CHIP, CLP(R), Prolog III and other systems, it is one which has returned with a new urgency because of the growing industrial interest in rapid solution of complex constraint problems. In this context, current CLP systems which are oriented towards OR such as ILOG Planner and 2LP will be discussed.

Some of the issues for CLP that these developments raise are (1) the need for progress on the implementation of cooperating solver engines, (2) the need for modeling frameworks to bridge the gap between mathematicians and programmers, (3) the need for research into meta-analysis of the most appropriate algorithmic solution to an application presented through a high-level API, (4) the need to make design decisions on languages vs librairies, and more.

References

1. DeBacker, B.; Beringer, H.: Combinatorial Problem Solving in Constraint Logic Programming with Cooperating Solvers, Logic Programming: Formal Methods and Practical Applications, edited by C. Beierle and L. Plümer,
2. Bockmayr, A.; Kasper, T.: A Unifying Framework for Integer and Finite Domain Constraint Programming, Max-Planck-Institut Technical Report MPI-I-97-2-008, 1997
3. ILOG Planner User's Manual, 1997
4. Mackworth, A. K.; Freuder, E. C.: The complexity of constraint satisfaction revisited. Artificial Intelligence 25:6574 (1993)
5. McAloon, K.; Tretkoff, C.: Optimization and Computational Logic. John Wiley & Sons 1996
6. McAloon, K.; Tretkoff, C.: Logic, Modeling and Programming. Annals of Operations Research 71:335-372 (1997)
7. McAloon, K.; Tretkoff, C., G. Wetzel: Disjunctive Programming and Cooperating Solvers, Advances in Computational and Stochastic Optimization, Logic Programming and Heuristic Search, edited by D.L. Woodruff, Kluwer 1997