FWO-Project Termination Analysis for Constraint Handling Rules
Project partner of K.U. Leuven, Belgium, 2008-2011.
In this project, we aim to develop several new, powerful techniques for
termination analysis of CHR.
Our main target is to develop techniques that are able to deal with a much
large class of programs
than what is currently the case. In particular, programs with propagation and
simpagation rules should be in the scope of the new approach.
We will port a number of recent techniques, developed in the context of Term
Rewrite Systems,
such as dependency pairs, and apply them to obtain powerful termination
analyzers for CHR.
We will also adapt abstract interpretation for CHR to better support
termination analysis.
Finally, we will develop prototype systems for the most promising techniques
developed in the project.
We will set up a benchmark of CHR programs that form a challenge for
termination analysis and
we will test the implemented prototypes on this benchmark.
More...
FWO-Project Platform independent analysis and implementation of Constraint Handling Rules
Project partner of K.U. Leuven, Belgium, 2007-2010.
This project intends to study and develop new analysis and implementation
techniques for the language CHR. The project will focus in particular on the
design of an abstract machine for CHR, the optimizing compilation of CHR by
means of abstract interpretation, the study of complexity (space and time)
properties of CHR and the study of techniques for compile time memory reuse.
More...
GLOB-CON - Rule-Based Propagation of Global Constraints
DFG Project FR 1390/1-1,
June 2006-2008.
Project partner is Dr. Sebastian Brand,
Melbourne University, Australia.
The project is concerned with the formally correct and efficiently executable
specification of constraint propagation for complex, global constraints by means
of rules.
A constraint satisfaction problem consists of a set of
constraints which must be satisfied by every solution.
Problems of this type, including NP-complete ones,
can be solved well by
problem simplification methods -- constraint propagation --
combined with search.
Notably constraint-specific propagation methods
can cause huge reductions of the search space at low cost,
drastically reducing the solving time in turn.
Specification as well as correct implementation of such methods
requires substantial expertise, however.
Rules have proved to be a useful formalism for the description of the
propagation of primitive, simple constraints. Appropriate rule-based languages,
notably Constraint Handling Rules, and corresponding implementations exist in
which constraint propagation procedures can immediately be executed. Several
methods for generating propagation rules automatically from declarative
definitions of primitive constraints have been developed in the last years.
The purpose of this project is to investigate
the specification of the propagation of global constraints by rules,
and
the automatic generation of rule-based constraint propagation mechanisms
for such constraints.
This project proposal
pursues the classical ideal of generating practical programs from
formal specifications.
ROARS - Reuse-Oriented Automated Reasoning Software
DAAD Probral and CAPES Project 415-br-probral/po/D05/30354,
March 2006-2008.
Project partners are Prof. Dr. Jacques Robin,
Universidade Federal do Pernambuco (CInUFPE), Recife, Brazil,
and Prof. Dr. Colin Atkinson, University of Mannheim, Germany,
and Dr. Armin Wolf, Fraunhofer FIRST, Berlin, Germany.
The project aims to create the first inter-institutional research group
worldwide to investigate the cross-fertilization between reuse-oriented software
engineering and application-embedded automated reasoning based on constraints
and rules. Main issues are the meta-model and formal logic semantics of a hybrid
object-oriented, rule-based constraint language to mediate between UML models
and Java or C implementations to create reusable and extensible rule-based AR
components for deduction, abduction, belief revision, inheritance, finite domain
constraint solving and their seamless integration.
More about ROARS.
CHR - The Constraint Handling Rules Language (CHR)
We are developing a special purpose language for writing constraint-based
systems called Constraint Handling Rules (CHR). Many CHR libraries exist
in declarative languages such as
Prolog, Java and Haskell, worldwide more than 100 projects and 500 publications
use CHR.
CHR Home Page
JCK - Java Constraint Kit
IB-BMBF/SCyT Project ARG 030/98 INF:
Java Constraint Kit, 1999-2002, project
applicant and project leader till 2001.
The main goal of the joint project is to develop a Java-based software
tool for solving combinatorial, optimization and planning problems
using constraint technology. Towards this end, we will implement a
constraint logic programming kit in the internet programming language
Java. Our choice of Java will allow easy implementation and
wide-spread use of the tool. The concrete target of the JCK project
is to embed the Constraint Handling Rules (CHR) into the JavaLog
programming language. CHR is a special language for the description of
constraint systems whereas JavaLog is an implementation of Prolog in
Java.
JCK Java Constraint Kit
FLPC - Functional Programming with Constraints
DFG project Wi 841/4-1:
Funktional-logische Programmierung
mit Constraints, 1996-2002, project co-applicant and project leader.
The goal of the project is the semantically well-founded integration
of functional, logic and constraint-based programming, the
implementation of a prototype language, the use and validation of the
language in application studies and finally the development of a
programming methodology.
DExVal - Simulating and Analyzing Hybrid Systems
IB-BMBF/CNPQ project: Formal Derivation of Meaningful Validation Experiments,
1998-2000, project co-applicant and project leader.
We work on a tool to derive validation and testing tasks of software
derived from formal specifications. The basis of our approach is the
abstract execution of hybrid systems (including statecharts) in a
constraint logic programming language. It is possible to run the
hybrid system abstractly, i.e. without giving values to initial
variables at all. Moreover, any variable in any state can be
constrained. The programm then produces all valid runs possible that
satisfy the given constraints on the variables. The result of a run
are time-dependent constraints that must be satisfied by the variables
of the hybrid system at different instances of time.
A. E. M. Ciarlini and T. Frühwirth, Automatic Derivation of Meaningful
Experiments for Hybrid Systems, ACM SIGSIM Conference on AI, Simulation and
Planning (AIS'2000), Tucson, Arizona, USA, March 2000.
Paper,
Slides.
ZEITRAUM - Spatio-temporal Reasoning for GIS
DAAD Project 314-VIGONI-DR:
Spatio-temporal Reasoning for GIS, 2000-2001, project
applicant and project leader.
Together with the University of Pisa we aim
at the development of new techniques to support spatio-temporal
reasoning in databases, in particular geographic information systems
(GIS), on the basis of constraint logics and constraint databases. The
TACLP approach of Dr. Frühwirth shall be extended by spatial
aspects and shall be integrated in deductive data models. In this way,
we expect an improvement in the application-oriented representation of
spatio-temporal relationships and the user-friendly integration and
interaction of heterogeneous data models and information sources for
problem solving.
TACLP - Temporal Annotated Constraint Logic Programming
A family of logics and associated programming languages for
representing and reasoning about time is introduced. The family is
conceptually simple while allowing for different models of time.
Formulas can be labeled with temporal information using
annotations. Both qualitative and quantitative (metric) temporal
reasoning about definite and indefinite information with time points
(instants) and time periods (temporal intervals) in different models
of time are supported. The important property of the logics is that
there is a systematic way to make their clausal fragment executable as a
constraint logic program.
Temporal Annotated Constraint Logic Programming,
Journal of Symbolic Computation, Special issue on Executable Temporal
Logics (M. Fisher, M. Orgun and S. Kono, Eds.),
Vol. 22, pp. 555-583, Academic Press, 1996,
Paper (ps.Z).
POPULAR - Planning Cordless Communication
The versatility of CHR has been shown in a
real-life application for SIEMENS
involving geometric reasoning to find the optimal placement of
senders for wireless portable devices (e.g. phones). Given a
blue-print of the building and information about the materials used
for walls and ceilings, POPULAR computes the minimal number of
transmitters and their location by simulation and subsequent
constraint-based optimization. This tool was regarded as one of the
most innovative applications in telecommunications by IEEE Expert
Magazine.
POPULAR won the Telecom application contest of Telecom Italia at CP'98,
the annual conference on constraint programming, in October 1998.
More...
MRA - The Munich Rent Advisor
This real-life application brings constraints to the internet.
It is a small expert system that allows one to calculate the typical
rent of a flat in Munich based on your input to a questionnaire.
The Munich Rent Advisor (MRA) won the prize for best application at
JFPLC, Clermont Ferrand, France, June 1996.
The MRA was shown at the SYSTEMS 96 and SYSTEMS 97
Computer Shows in Munich, Germany,
and featured in several newspaper articles and AI Watch, UK.
10000's of requests have been served.
More...
CHIC
ESPRIT #5291, Constraint Handling in Industry and Commerce, 1991-95. Development of a programming methodology for constraint languages and its application in industry.
LAC
ESPRIT #7035, Logic and Change, 1994-96. Research in non-monotonicity and temporal change in logics and its application in programming languages.
IDEA
ESPRIT #6333, Intelligent Database Environment for Advanced Applications, 1995. Development of an object-oriented deductive database system.
EQUATOR
ESPRIT #2409, Environment for Qualitative Temporal Reasoning, 1992-93. Development and application of temporal reasoning to air traffic control and urban traffic control.
Ph.D. Grants
Fulbright grant and Austrian chamber of commerce grant, 1989-1990 for research stay with Prof. Dr. D. S. Warren, Computer Science Department, State University of New York at Stony Brook, USA.
VIP-DBS
Austrian National Bank Grant #2791, A Deductive Database Management System (in German), 1984-86. Development of a deductive database system at the Technical University of Vienna.
Thom Frühwirth, updated November 20 2008