One day during July 24-28, 2000, Imperial College, London, UK
at the First International Conference on Computational Logic
(CL2000)
Rule-based formalisms are ubiquitous in computer science, and even more so in constraint reasoning and programming. In constraint reasoning, algorithms are often specified using inference rules, proof rules, rewrite rules, sequents or logical axioms. Advanced programming languages like CHR, CLAIRE and ELAN allow the implementation both constraint solvers and programs using constraints in a rule-based formalism.
The workshop invites papers describing ongoing work in using rule-based formalisms in constraint reasoning and programming. In particular, on specification of algorithms for solving constraints by rules and on implementations of constraint solvers and programs solving problems in a novel way using rule-based programming languages that go beyond constraint logic programming, as well as on analysis of rule-based programs and other issues related to rule-based language design and implementation.
Wed, July 26
2:30 - 4:00 Session 1
Toward an Adaptive Solution of Dynamic Constraint Hierarchies Over Finite Domains
Armin Wolf
In the past, we presented a method to solve constraint hierarchies
over finite domains that are based on nontrivial error functions. This
earlier work is extended here: a new incremental algorithm is
presented that keeps ordinary constraint systems equivalent to dynamic
constraint hierarchies. More specifically, hierarchies of
inequalities over finite integer domains are transformed into
equivalent constraint systems that are adapted whenever these
hierarchies change. Unlike other approaches, a nontrivial error
function determines the solutions of the hierarchies. The presented
adaptation algorithm is based on known incremental algorithms that
adapt {\em Constraint Handling Rule\/} ({\sf CHR}) derivations after
addition or deletion of constraints. These algorithms are shown to be
still useful for solving dynamically changing constraint
hierarchies. The presented adaptation algorithm is truly incremental
and efficient, because only those parts of considered constraint
problems are adapted that have to be. This helps avoid superfluous
recalculations that would result from a complete re-evaluation from
scratch.
Download Paper
Programming Constraint Propagation in Reactive Rules
Neng-Fa Zhou
Constraint propagation is the most widely used constraint-solving technique
in constraint programming. Since there are a variety of domains and
propagation rules, it is difficult to implement efficient constraint solvers
in low-level languages. Past experience tells us that providing a set of
built-in constraints alone is unsatisfactory, and a constraint language
should offer users high-level constructs for programming constraint
propagation rules directly. In this paper, we present a rule-based
high-level language, called APEARL, for constructing reactive systems such
as constraint propagators. APEARL combines the goal-oriented execution model
of logic programming with the event-driven execution model. This hybrid
execution model facilitates programming agents that are reactive to the
environment. The focus of this paper is to show how to implement constraint
propagators for various domains including trees, finite-domains, and sets.
These examples demonstrate the power of APEARL. A subset of the language has
been implemented and the experimental results are very promising.
Download Paper
Constraint compiling into rules formalism for dynamic CSPs computing.
Sylvain Piechowiak and J. Rodriguez
In this paper we present a rule based formalism for filtering variables domains of constraints.
This formalism is well adapted for solving dynamic CSP. We take diagnosis as an instance problem to
illustrate the use of these rules. A diagnosis problem is seen like finding all the minimal sets of constraints
to be relaxed in the constraint network that models the device to be diagnosed.
Download Paper
4:00 - 4:30 Coffee Break
4:30 - 5:00 Session 2
CHR and Harrop formulas
Yoann Padioleau and Olivier Ridoux
We propose an integration of Constraints Handling Rules (CHR) and Harrop
formulas. Implication in goals offers a means for dynamically loading
CHR rules, and for augmenting the constraint store. Constraints in
goals are checked against the current store, but do not augment the
store. Universal quantifier in goals offers a means for introducing new
constrained variables. The neat effect of this integration is that the
constraint store is more like a LambdaProlog program than like a Prolog
goal. In particular, consistency checking (when augmenting the store)
and entailment (when checking a constraint against the store) are
clearly distinguished. This helps among other things in making
different solvers cooperate. A high-level implementation is sketched.
It uses in a critical way a feature of the Prolog/Mali implementation of
LambdaProlog called substitutable terms.
Download Paper
Type Classes and Constraint Handling Rules
Kevin Glynn, Peter J. Stuckey and Martin Sulzmann
Type classes are an elegant extension to traditional, Hindley-Milner
based typing systems. They are used in modern, typed languages such as
Haskell to support controlled overloading of symbols. Haskell 98
supports only single-parameter and constructor type classes. Other
extensions such as multi-parameter type classes are highly desired but
are still not officially supported by Haskell. Subtle issues arise
with extensions, which may lead to a loss of feasible type inference
or ambiguous programs. A proper logical basis for type class systems
seems to be missing. Such a basis would allow extensions to be
characterised and studied rigorously. We propose to employ Constraint
Handling Rules as a tool to study and develop type class systems in a
uniform way.
Download Paper
Constraint Exploration and Envelope of Simulation Trajectories
Oswaldo Terán , Bruce Edmonds and Steve Wallis
The implicit theory that a simulation represents is precisely not in the
individual choices but
rather in the ?envelope? of possible trajectories - what is important is
the shape of the whole
envelope. Typically a huge amount of computation is required when
experimenting with
factors bearing on the dynamics of a simulation to tease out what
affects the shape of this
envelope. In this paper we present a methodology aimed at systematically
exploring this
envelope. We propose a method for searching for tendencies and proving
their necessity
relative to a range of parameterisations of the model and agents?
choices, and to the logic of
the simulation language. The exploration consists of a forward chaining
generation of the
trajectories associated to and constrained by such a range of
parameterisations and
choices. Additionally, we propose a computational procedure that helps
implement this
exploration by translating a Multi Agent System simulation into a
constraint-based search
over possible trajectories by ?compiling? the simulation rules into a
more specific form,
namely by partitioning the simulation rules using appropriate modularity
in the simulation.
An example of this procedure is exhibited.
Download Paper
Fri, July 28
10:00 - 10:30 Coffee Break
10:30 - 13:00 Session 3
Chair: Krzysztof Apt
Checking, Fixing, and Transforming Information using Rule-Based
Constraint Reasoning
Invited Talk by Eric Monfroy
In transforming information from one source to another, there is a
growing need for tools that help understand the structure of existing
data, in order to preserve its meaning. We developed a method, using a
predicate syntax, to describe data-structures. This helps both engineer
and customer to reason about the information, both structure and
content, in an easy way. We then use the resulting specifications for
fast implementation in ECLiPSe and CHR (Constraint Handling Rules). This
enables us to fix and transform data with little effort, even when the
structure of the data source is not completely clear at first. It proves
to be a successful way to produce a simple specification, and thus
readable by both engineer and customer, which can be converted into an
implementation with little effort. This implementation can be used for
checking, fixing and transforming the content of an existing database.
Towards a Methodology for Solving Constraints Using a Rule-Based Approach
Carlos Castro
Download Paper
Applying Constraint Handling Rules to HPSG
Gerald Penn
Constraint Handling Rules (CHR) have provided a realistic solution to
an over-arching problem in many fields that deal with constraint logic
programming: how to combine recursive functions or relations with
constraints while avoiding non-termination problems. This paper
focuses on some other benefits that CHR, specifically their
implementation in SICStus Prolog, have provided to computational
linguists working on grammar design tools. CHR rules are applied by
means of a subsumption check and this check is made only when
their variables are instantiated or bound. The former functionality
is at best difficult to simulate using more primitive coroutining
statements such as SICStus when/2, and the latter simply did not exist
in any form before CHR.
For the sake of providing a case study in how these can be applied to
grammar development, we consider the Attribute Logic Engine (ALE), a
Prolog preprocessor for logic programming with typed feature
structures, and its extension to a complete grammar development system
for Head-driven Phrase Structure Grammar (HPSG), a popular
constraint-based linguistic theory that uses typed feature structures.
In this context, CHR can be used not only to extend the constraint
language of feature structure descriptions to include relations in a
declarative way, but also to provide support for constraints with
complex antecedents and constraints on the co-occurrence of feature
values that are necessary to interpret the type system of HPSG
properly.
Download Paper
Security Policy Consistency
Carlos Ribeiro, Andre Zuquete, Paulo Ferreira and Paulo Guedes
With the advent of wide security platforms able to express
simultaneously all the policies comprising an organization's
global security policy, the problem of inconsistencies within
security policies become harder and more relevant.
We have defined a tool based on the CHR language which is able to
detect several types of inconsistencies within and between
security policies and other specifications, namely workflow
specifications.
Although the problem of security conflicts has been addressed by
several authors, to our knowledge none has addressed the general
problem of security inconsistencies, on its several definitions
and target specifications.
Download Paper
To submit, send an email to fruehwir@informatik.uni-muenchen.de with the subject line "CL2000 rules" containing three ASCII lines with title, author(s) and WWW link to compressed postscript file (5-15 pages). Accepted papers will be published in hard-copy proceedings (available at the workshop) and in electronic form at the Computing Research Repository (CoRR).
The final workshop programme schedule will be coordinated with the UK Constraint Network (Consnet) Annual Workshop.