Second Seminar Day on Constraint Handling Rules am 6. Juli 2006

Constraint Handling Rules (CHR) ist eine einfache aber elegante, deklarative, regelbasierte Programmiersprache. Sie verbindet Bestandteile der Constraint-Programmierung, Produktionsregeln und Ersetzungssysteme. Typische Anwendungen sind Constrainlösen, natürliche Sprachverarbeitung, Typüberprüfung und Schließen in Multiagentensystemen. Es gibt verschiedene Implementierungen von CHR für Prolog, Java und andere Sprachen. Nach dem erfolgreichen First Seminar Day am 10. Mai 2006 der Declarative Languages and Artificial Intelligence research group (DTAI) der K.U.Leuven (Belgien) wird der Second Seminar Day von der Ulmer CHR-Forschungsgruppe veranstaltet. Anläßlich des Ulmer Besuchs von Slim Abdennadhers Forschungsgruppe aus der German University in Cairo lädt der Erfinder von CHR Thom Frühwirth ein, um neue Ergebnisse vorzustellen und Ideen auszutauschen.

Programm

  • 09:00 CHR Tutorial. Thom Frühwirth, Universität Ulm.
  • 10:15 ARM: Automatic Rule Miner. Noha Salem, German University in Cairo.
  • 10:45 Pause.
  • 11:00 Linear Logic Semantics for CHRv. Hariolf Betz, Universität Ulm.
  • 11:30 Solving general first order constraints. Khalil Djelloul, Universität Ulm.
  • 12:00 Mittagessen.
  • 14:30 Implementation of an F-Logic Kernel in CHR. Martin Käser, Universität Ulm.
  • 15:00 Complexity of the CHR Rational Tree Equation Solver. Marc Meister, Universität Ulm.
  • 15:30 Pause.
  • 15:45 Cairo teaching assistants' interests (10 min each, informal). Noha Salem, Amira Thabet, Ingi Sobhi, Abdellatif Olama, German University in Cairo.
  • 16:30 Cairo students' projects using Constraint Programming (10 min each, informal). Amira Gamaleldin, Marlien Edward, Mounir Stino, German University in Cairo.
  • 17:00 Abschließende Diskussion.

Näheres zu den Vorträgen

  • CHR Tutorial. <LINK 5731>Thom Frühwirth</LINK>, Universität Ulm. Rule-based programming experiences renaissance due to its applications in areas such as Business Rules, Semantic Web, Computational Biology, Verification and Security. Executable rules are used in declarative programming languages, in program transformation and analysis, and for reasoning in artificial intelligence applications. Constraint Handling Rules (CHR) is a concurrent committed-choice constraint logic programming language consisting of guarded rules that transform multi-sets of atomic formulas (constraints) into simpler ones until exhaustion. CHR was initially developed for solving constraints, but has matured into a general-purpose concurrent constraint language over the last decade, because it can embed many rule-based formalisms and describe algorithms in a declarative way. The clean semantics of CHR facilitates non-trivial program analysis and transformation.
  • ARM: Automatic Rule Miner. Noha Salem, German University in Cairo. Rule-based formalisms are ubiquitous in computer science. However, a difficulty that arises frequently when specifying or programming the rules in to determine which effects should be propagated by these rules. In this paper, we present a tool called ARM (Automatic Rule Miner) that generates rules for relations over finite domains. ARM offers a rich functionally to provide the user with the possibility of specifying the admissible syntactic forms of the rules. Furthermore, we show that our approach performs well on various examples, e.g. generation of firewall rules or generation of medical diagnosis rules. Thus, it is suitable for users from different fields.
  • Linear Logic Semantics for CHRv. <LINK 5746>Hariolf Betz</LINK>, Universität Ulm. Declarative semantics presents a powerful tool for the analysis and verification of CHR programs, a property inherited from its logical and constraint-logical predecessors. My talk is about the linear logic semantics for CHRv, i.e. CHRs with disjunction. At first, a short introduction to linear logic will be given and the already established linear logic semantics for classic CHR will be presented. Subsequently, we will discuss my approach how to extend this result to CHRv.
  • Solving general first order constraints. <LINK 5753>Khalil Djelloul</LINK>, Universität Ulm. We show in this talk how can we generalise the elementary notion of "a constraint" to "a general first order formula" with functions, relations and any logical symbols. By the same way, we generalize the notion of solving a constraint in any model M to solving a first order formula in any theory T that has at least M as model. In order to solve a first order constraint P in a theory T, we first introduce the notion of "decomposable theories" and show that a lot of fundamental theories used in computer science are "decomposable". We give then a general algorithm for solving first-order formulas in any decomposable theory T. The algorithm is given in the form of five rewriting rules. It transforms a first-order formula P, which can possibly contain free variables, into a conjunction Q of solved formulas easily transformable into a Boolean combination of existentially quantified conjunctions of atomic formulas. In particular, if P has no free variables then Q is either the formula true or false. The correctness of our algorithm proves the completeness of the decomposable theories.
  • Implementation of an F-Logic Kernel in CHR. Martin Käser, Universität Ulm. Frame-Logic is an extension of classical predicate logic which accounts in a declarative way for many features of object-orientation. This talk presents a concise, exploratory CHR implementation of Frame-Logic's core features, based on data-driven forward propagation, including object-oriented constraint syntax, type-checking, and interaction of Frame-Logic deduction with non-monotonic overriding by inheritance.
  • Complexity of the CHR Rational Tree Equation Solver. <LINK 5740>Marc Meister</LINK>, Universität Ulm. One of the first CHR programs is the classic constraint solver for syntactic equality of rational trees that performs unification. The worst-case time (and space) complexity of this short and elegant solver so far was an open problem and assumed to be polynomial. In this talk we (this is joint work with Thom Frühwirth) show that under the standard operational semantics of CHR there exist particular computations with n occurrences of variables and function symbols that produce O(2^n) constraints, thus leading to exponential time and space complexity. We also show that the standard implementation of the solver in CHR libraries for Prolog may not terminate due to the Prolog built-in order used in comparing terms. Complexity can be improved to be quadratic for any term order under both standard and refined CHR semantics without changing the equation solver, when equations are transformed into flat normal form.

Lehrassistenten der German University of Cairo und ihre Interessen (jeweils 10 Minuten)

  • Noha Salem. Theoretical aspects of CHR, preflow push algorithm, analysis of confluence and other performance criteria, automatic generation of rules (ARM tool).
  • Amira Thabet. Business rules and JCHR, automatic generation of rules (ARM tool).
  • Ingi Sobhi. Business rules, Prolog and CHR, global constraints in CHR.
  • Abdellatif Olama. Global constraints in JCHR, automatic generation of Rules (ARM tool).

Studenten der German University of Cairo und ihre Projekte (jeweils 10 Minuten)

  • Amira Gamaleldin. Examination scheduling.
  • Marlien Edward. Timetable scheduling for advising students.
  • Mounir Stino. Timetable scheduling for all students.