The CHR Working Week is held at Ulm University from October, 5th to October, 9th. It aims to bring together researchers and practitioners of Constraint Handling Rules and related areas. The program features invited talks from leading CHR researchers as well as from company representatives.

Furthermore, undergraduate and PhD students are invited to participate and information on sponsorship and internship programs is provided for them. PhD students of related fields are invited to present their research and discuss it with other expert attendees.

Finally, discussion sessions provide possibilities for participants to identify common interests and initiate future cooperations.

All talks will be given in room O28/1002.

Research Topics:

• Thom Frühwirth - CHR Projects and Research Topics (Slides)

  An overview of the topics currently of interest to our CHR research group, as well as planned and ongoing projects.

• Jairson Vitorino - Model-Driven Engineering a Versatile, Extensible, Scalable Rule Engine through Component Assembly and Model Transformations (Slides)
  

  My proposal takes CHR engines a step beyond, by designing a new CHRv engine (CHROME, *Constraint Handling Rule Online Model-driven Engine*) and a corresponding compiler using a component-based model-driven approach. It is the first CHRv engine with an efficient and complete search algorithm (e.g. the conflict-directed backjumping algorithm), the first versatile rule-based engine, integrating production rules, rewrite rules, its built-in belief revision mechanism (reused for handling disjunctions) and CLP rules to run on top of a mainstream object-oriented (OO) platform (Java). Because it is the first rule-based engine following a component-based model-driven approach, it allows easy porting to other OO platforms such as Python, JSP, C++ and others. Finally the compiler is the first that uses a model transformation pipeline to transform from a source relational-declarative language into a OO-imperative paradigm language.

• Peter van Weert - JCHR Tutorial (PP-Slides, PDF-Slides)

  A tutorial on the usage and capabilities of JCHR - a Java implementation of Constraint Handling Rules.

• Peter van Weert - CHR Implementation Techniques (PP-Slides, PDF-Slides)

  Constraint Handling Rules (CHR) is a powerful, high-level programming language based on multi-headed multiset rewrite rules. In recent years, CHR has matured to a powerful general purpose language, increasingly used for applications such as constraint solving, computational linguistics, and multi-agent systems. Considerable research has therefore been devoted to the efficient compilation and execution of CHR programs, resulting in several very efficient CHR systems for Prolog, Java, C, and Haskell.
  
  This tutorial provides a lucid, comprehensive overview of the efficient compilation and optimization techniques used by current state-of-the-art CHR systems. Using high-level pseudocode and clarifying examples, we first introduce the fundamental lazy rule evaluation methodology, and then gradually the more advanced analysis and optimization techniques. We briefly compare our approach with the popular Rete matching algorithm, and touch upon ongoing and future CHR implementation research.

• Jon Sneyers - Computational Complexity of CHR (Slides)

  We investigate the CHR programming language from the point of view of computational complexity theory. In particular, we prove a complexity-wise completeness result. We show that the CHR language and its state-of-the-art implementations (i.e., CHR systems that implement the most important compiler optimizations) are “sufficiently” efficient in the following precise sense: every algorithm can be implemented in CHR and be executed with the optimal asymptotic time and space complexity (simultaneously).

• Jon Sneyers - CHR Tutorial (Slides, Handouts)

  Constraint Handling Rules (CHR) is a high-level programming language based on multi-headed, committed-choice, guarded multiset rewrite rules. In recent years, CHR has matured to a powerful general purpose language, increasingly used for applications such as constraint solving,  computational linguistics, and multi-agent systems.
  
  CHR is the only declarative language known in which every algorithm can be implemented with optimal space and time complexity. This talk shows attendants CHR's strengths as a programming language and how to use CHR for solving problems quickly and elegantly. Simple examples teach how to write and reason about CHR programs, and what problems one can solve effectively with CHR.

• Frank Raiser - State Equivalence and Persistent Constraints (Slides)

  This talk highlights recent research results on fundamentals of the CHR operational semantics: a new axiomatic definition of state equivalence is given from which a simplified formulation of CHR's operational semantics is derived. We present a novel interpretation of the semantics as a rewrite system over equivalence classes that has interesting features for program analysis and proofs.

  Furthermore, we introduce persistent constraints, which represent an arbitrary number of rule firings in a finite way. Defining CHR's transition system over equivalence classes in an irreflexive manner is an alternative approach to avoid trivial non-termination of propagation rules. We discuss examples that highlight the different operational behavior.

Research Presentations:

• Andrea Triossi - Trigger Systems (Slides)

  A trigger system is a sub detector element common to all the experiments of particle, astroparticle and nuclear physics. It uses simple criteria to rapidly decide which events in a detector to keep when only a small fraction of the total can be recorded. A multi-level triggering philosophy is fundamental to the concept of powerful modern trigger processing. Typically a low level trigger run in electronics on the detector and some high level trigger stages are software based and runs on computer cluster. Reconfigurable computing is intended to fill the gap between hardware and software, achieving potentially much higher latency related performance than software, while maintaining a higher level of flexibility than hardware. Declarative programming languages can be used to describe properties belonging to a particular trigger system, to verify them through functional verification and eventually to directly implement it on a Field Programmable Gate Array.

• Jacopo Mauro - Expressive Power of CHR with Rule Priorities (Slides)

  Recently CHR has been extended introducing userdefinable (static or dynamic) rule priorities. The resulting language, called CHRrp, allows a better control over execution while retaining a declarative and flexible style of programming. We will show that dynamic priorities do not augment the expressive power by providing an encoding of dynamic priorities into static ones. Then we will show that, when considering the theoretical operational semantics, CHRrp is strictly more expressive than CHR.

• Massimiliano Cattafi - Combinatorial Optimization Problems and Examples (Slides)

  Optimization in combinatorial problems is a well studied subject in Artificial Intelligence and Operational Research. The benefit in applying knowledge and techniques achieved in this area to those (suitable) real life cases which are (presumably) not, at present, addressed in the most effective way is twofold: we could solve them faster or in a better way and gain useful information to enhance the aforementioned knowledge and techniques. An example, along with possible strategies to address it, will be shown.

• Giovanni Bacci - Abstract Interpretation and Functional Logic Languages (Slides)

  Curry is an universal programming language aiming at the amalgamation of two declarative programming paradigms, namely functional programming and logic programming. In these years Curry received a considerable attention, both from the practical and from the theoretical side. Nevertheless, there are several aspects of the Curry semantics which have not been clarified yet. In particular, no compositional semantics for Curry has been defined so far.
  We introduce a fix-point semantics which characterizes the I/O behavior of a first-order Curry program which is compositional and goal-independent, that is, which allows to retrieve the semantics of any (not necessarily ground) goal from the semantics of its components.
  Moreover, using standard techniques from Abstract Interpretation, we give an abstract semantics which is precise with respect to the I/O behavior. Remarkably, the proposed abstract semantics is independent from the choice of the used definitional tree set. Such semantics can be used as a basis to define both incremental and modular analysis and verification tools.

Companies / Organisations:

• Roland Stelzer - Robotic Sailing (Slides)

  Robotic sailing boats execute the complex sailing processes completely autonomously and without human interaction. Starting with the calculation of the optimal route based on weather data, to the autonomous execution of manoeuvres, robotic boats are able to reach any desired destination by analysing sensor data in real-time.

  The talk presents the autonomous sailboat "ASV Roboat" of the Austrian Society for Innovative Computer Science (InnoC), which won several international competitions in robotic sailing. Project history, the underlying control architecture, as well as possible applications of robotic sailing technology will be covered.

• Institute of Media Informatics - TTable, Typotisch

  The "TTable" project was implemented within the Ubiquituous Computing Degree Course at the department of media and computer science at Ulm University. The project's main goal was the construction of a large yet affordable multitouch table, primarily designed for student and research use. We especially emphasized the fitness for daily use (e.g. for multitouch software development at a software dev lab) and comprehensive documentation as a solid base for entering the world of multitouch devices.
  
  The typotisch is a fusion of kinetic typography and a haptic user interface. According to the location of words placed on the table an animation is rendered enhanced with various effects. The effects depend on the semantic of each word.

• Uwe Lesta (SBS) - Robot Configuration (Slides)

  This talk presents a company project in the domain of robot configuration.

• Ralf Gerlich (BSSE) - Automatic Software Testing (Slides)

  Software test is one of the most important quality assurance measures in software engineering, allowing representative assessment of software quality, either on the target system itself (test-on-target) or at least a good approximation thereof (test-on-host).
  
  Unfortunately, testing is also very expensive, typically taking at least half of the project effort and cost when prepared and executed manually. Consequently, the potential for cost reduction by automation is high for software test.
  
  We present a new method for constraint-based automatic test data generation using graph-analytical methods on augmented control-flow graphs for prediction of control- and data-flow. Based on the experience gained during definition and implementation of the method we discuss beneficial and adversary issues found in applying tools and theoretical frameworks of classical CHR, CHRv and probabilistic CHR.

Sponsorship Programs:

• Frank Raiser - Sponsorship Programs (Slides)

  This talk is intended for PhD students and Post-Docs looking for funding. We will give an overview of the most important available sponsorship programs and present typical constituents of required applications.

• Roland Stelzer - Happylab - Der Raum zum Sachen machen (Slides)

  Hier wird das Happylab vorgestellt – Treffpunkt und Werkstatt für technikinteressierte Jugendliche und Erwachsene in Wien. Im Happylab können Ideen in entspannter Atmosphäre entstehen, diskutiert und sofort umgesetzt werden.
  
  Die Betreiber verstehen sich als offenes Netzwerk von Personen aus unterschiedlichsten Professionen mit dem gemeinsamen Ziel, den kreativen Umgang mit neuen Technologien zu fördern. Wissenschaft soll Spaß machen, erlebbar und begreifbar gemacht werden.

Demos:

• Jon Sneyers - Random Music Generation with CHRiSM

  This demo presents a tool that automatically generates random music based on CHRiSM - a combination of CHR and Prism.

• Johannes Langbein - CHR Confluence Checker

  A Prolog implementation of a confluence checker for CHR is presented. The demo also includes a checker for state equivalence of CHR states.

As part of our program we will treat our participants to a climb up the 768 steps of the tower of the Ulm Cathedral - the tallest church in the world. Participants may also join a guided tour through the beautiful city of Ulm, the birthplace of Albert Einstein.

Furthermore, we provide a joint dinner on Monday evening for everyone holding an invited talk during the CHR Working Week and organizers of the event.

Frank Raiser Program, Promotion, Local Organization

Thom Frühwirth Program, Invited Talks

Ulrike Seiter Local Organization, Accommodation