Cooperation and Coordination of Constraint Solvers
Though the paradigm of constraint programming
offers efficient
mechanisms to handle constraints of various domains, one constraint
solver can only handle constraints of a particular constraint system.
Thus, it is often desirable and advantageous to combine several
constraint systems and the associated constraint solving techniques
because this combination makes it possible to solve problems that none
of the single solvers can handle alone.
Thus, we proposed a general scheme for the cooperation of constraint
solvers.
The base of our system is a uniform interface for constraint solvers
which allows a fine-grain formal specification of information exchange
between constraint solvers.
On top of this interface, we developed an open and flexible combination
mechanism for constraint solvers.
The combination is open in the sense that whenever a new constraint
system with associated constraint solver (satisfying certain
properties) arises, it can be easily incorporated into the overall
system independently of its domain and the language in which the
constraint solver is implemented.
It is flexible because the definition of different strategies for the
cooperation of the single solvers is possible in a simple way.
|
Multiparadigm Programming Languages
In the area of
multiparadigm programming we are working at the following topics:
- integration of constraints and constraint
solvers into arbitrary declarative languages (multiparadigm constraint
programming),
- a formal description of a general integration
framework,
- prototypic implementations of multiparadigm
languages, like
the functional logic programming language Brooks which integrates
different narrowing strategies and the constraint-imperative language
Turtle amalgamating the constraint and imperative paradigms and
realizing furthermore typical constructs of functional languages
including higher-order functions, polymorphic modules and algebraic
data types.
|
Taskparallel
Skeletons for functional languages (finished 1998)
Algorithmic
skeletons
are polymorphic higher order functions.
They represent general parallelization patterns and are parallely
implemented.
Skeletons can be used for the integration of parallel applications into
sequential languages.
In this way it is possible to combine expressiveness and flexibility of
the sequential base language with the efficiency of parallel algorithms
for specific applications.
In dependence of the exploited parallelism we distinguish between data
parallel and task parallel skeletons.
|
|
Books
[HW07]
Hofstedt, P., Wolf, A.,
Einführung in die Constraint-Programmierung.
ISBN 3-540-23184-6. Springer-Verlag. (in german) To appear 2007.
[PH06]
Pepper, P., Hofstedt, P.,
Funktionale Programmierung: Sprachdesign und Programmiertechnik.
ISBN 3-540-20959-X. Springer-Verlag. 2006. (in german)
PhD
Thesis
[Hof01c] (PDF)
Hofstedt, P.: Cooperation and Coordination of Constraint
Solvers. Ph.D.Thesis. Shaker Verlag. Aachen 2001.
Edition of Workshop Proceedings
[MGH04] (PDF)
Muñoz-Hernández, S., Gómez-Pérez, J.M.,
Hofstedt ,P. (Eds.), WLPE 2004: 14th
Workshop on Logic
Programming Environments and
MultiCPL
2004: Third Workshop on Multiparadigm Constraint Programming Languages.
Saint-Malo, France, 2004.
[HHWAFL03] (PDF)
Hanus, M., Hofstedt, P., Wolf, A., Abdennadher, S., Frühwirth, T.,
Lallouet, A. (Eds.),
MultiCPL'03: Second International Workshop on Multiparadigm Constraint
Programming Languages and
RCoRP'03:
Fifth International Workshop on Rule-Based Constraint Reasoning and
Programming.
Workshop Proceedings. Kinsale, Ireland, 2003.
[HHAFW02] (PDF)
Hanus, M., Hofstedt, P., Abdennadher, S., Frühwirth, T., Wolf, A.
(Eds.), MultiCPL'02:
Workshop on Multiparadigm Constraint Programming Languages and
RCoRP'02: Fourth Workshop on Rule-Based Constraint Reasoning and
Programming.
Workshop Proceedings. Cornell University, Ithaca, NY, USA, 2002.
Refereed Journal Articles, Conference and Workshop Proceedings
[HP06]
Hofstedt, P., Pepper, P.: Integration
of Declarative and Constraint Programming. Journal on Theory and
Practice of Logic Programming -- TPLP. Special Issue on Multiparadigm Languages
and Constraint Programming. 7(1). To appear 2006.
[FHPR06]
Frank, St., Hofstedt, P., Pepper, P., Reckmann, D.:
Solution Strategies
for Multi-domain Constraint Logic Programs.
Perspectives of Systems Informatics -- PSI 2006, Revised Papers. Lecture Notes in Computer Science. Springer
Verlag. To appear 2006.
[HK06]
Hofstedt, P., Krzikalla, O.:
Turtle++ – A CIP-Library for C++.
16th International
Conference on Applications of Declarative Programming and Knowledge
Management
-- INAP 2005. Lecture Notes in Computer Science. Springer Verlag. To appear 2006.
[FH05]
Frank, St., Hofstedt, P.: CLFD: A
Finite Domain Constraint Solver in Common Lisp. International
Lisp Conference -- ILC.
Stanford University. Association of Lisp Users 2005.
[FHR05]
Frank, St., Hofstedt, P., Reckmann D.: System Description: Meta-S. Combining
Solver Cooperation and Programming Languages. 19th International
Workshop on (Constraint) Logic Programming -- W(C)LP. 2005.
[FHR04] (PDF)
Frank, St., Hofstedt, P., Reckmann, D.: Strategies for the Efficient Solution of
Hybrid Constraint Logic Programs. In MultiCPL'04: Third
Workshop on Multiparadigm Constraint Programming Languages. Saint-Malo,
France, 2004.
[GH03] (PDF)
Grabmüller, M., Hofstedt, P.: Turtle. A
Constraint Imperative
Programming Language. Twenty-third SGAI
International Conference on
Innovative Techniques and Applications of Artificial
Intelligence. Research and Development in Intelligent Systems XX.
Springer-Verlag 2003.
[FHM03a] (PDF)
Frank, St., Hofstedt, P., Mai, P.R.: Meta-S.
A strategy-oriented
Meta-Solver Framework. In Russel, I., Haller, S.: Proceedings of
the
Sixteenth International Florida Artificial Intelligence Research
Society Conference. AAAI Press 2003.
[FHM03b] (PDF)
Frank, St., Hofstedt, P., Mai, P.R.: A
Flexible
Meta-solver Framework for Constraint Solver Collaboration.
In Günter, A., Kruse, R. and
Neumann, B.: Proceedings of the 26th German Conference on Artificial
Intelligence, KI'2003. Volume 2821 of LNCS. Springer-Verlag 2003.
[FHM03c]
Frank, St., Hofstedt, P., Mai, P.R.: A
Case Study on Termination. In
Albert Rubio (Ed.): Proceedings of the 6th International Workshop on
Termination, WST'03. Technical Report DSIC-II/15/03, Departamento de
Sistemas Informáticos y Computación, Universidad
Politécnica de Valencia, 2003.
[HM03] (PDF)
Hofstedt, P., Metzner, A: Multiple
Evaluation Strategies for the
Multiparadigm Programming Language Brooks. In Germán
Vidal
(Ed.): Proceedings of the 12th International Workshop on Functional and
(Constraint) Logic Programming, WFLP'03. Technical Report
DSIC-II/13/03, Departamento de Sistemas Informáticos y
Computación, Universidad Politécnica de Valencia, 2003.
[Hof02] (PDF)
Hofstedt, P.: A general Approach for
Building
Constraint Languages. In B. McKay and
J. Slaney (Eds.), AI 2002: Advances in Artificial Intelligence.
15th Australian Joint Conference on Artificial Intelligence.
Canberra, Australia.
Volume 2557 of LNCS. Springer-Verlag 2002.
[GHW02] (PDF)
Gips, C., Hofstedt, P., Wysotzki, F.: Spatial
Inference - Learning
vs. Constraint Solving. In M. Jarke, J.
Köhler, G. Lakemeyer (Eds.),
KI 2002: Advances in Artificial Intelligence.
Volume 2479 of LNCS. Springer-Verlag 2002.
[Hof01a]
Hofstedt, P.: Declarative Host
Languages for Constraint Systems.
International Symposium on Artificial Intelligence. ISAI'2001.
[HSG01] (PDF)
Hofstedt, P., Seifert, D., Godehardt, E.: A Framework for Cooperating
Constraint Solvers - A Prototypic Implementation.
Workshop on Cooperative Solvers in Constraint Programming - CoSolv. At
the Seventh International Conference on Principles and Practice of
Constraint Programming. 2001.
[Hof00a] (PDF)
Hofstedt, P.: Cooperating Constraint
Solvers. Sixth International
Conference on Principles and Practice of Constraint Programming - CP
2000. Volume 1894 of LNCS. Springer-Verlag 2000.
[Hof00b] (PDF)
Hofstedt, P.: Better Communication
for Tighter Cooperation. Lloyd et
al. (Eds.), First International Conference on Computational Logic - CL
2000.
Volume 1861 of LNCS. Springer-Verlag 2000.
[Hof98d] (PDF)
Hofstedt, P.: Task Parallel
Skeletons for Irregularly Structured
Problems. In D.Pritchard and J.Reeve (Eds.), Euro-Par'98 -
Parallel
Processing, 4th International Euro-Par Conference, Southampton.
Volume 1470 of LNCS. Springer-Verlag 1998.
Some Unrefereed
Publications
[FGHM03] (PDF)
Frank, St., Grabmüller, M., Hofstedt, P., Metzner, A.:
Constraints, Predicates, Functions,
and a Turtle. 20. Workshop der
GI-Fachgruppe "Programmiersprachen und Rechenkonzepte". 2003.
[Hof01b] (PS.GZ)
Hofstedt, P.: How to integrate
Declarative Languages and Constraint
Systems. In: K.Indermark, Th.Noll (Eds.), Kolloquium
Programmiersprachen. Technical Report AIB-2001-11. RWTH Aachen. 2001.
[HS97]
Hofstedt, P., Schwigon, S.: Methoden
zur automatischen Parallelisierung
(Constraint-) logischer Programme.
Technical Report TUD-FI97-08, Oktober 1997, Dresden University of
Technology. (in german).
[Hof97] (PS.GZ)
Hofstedt, P.: Taskparallele Skelette
für irregulär
strukturierte Probleme in deklarativen Sprachen. Aachener
Informatik -
Berichte AIB 97-7, RWTH Aachen, Fachgruppe Informatik. (in german).
[Hof95]
Hofstedt, P. Eine abstrakte Maschine für eine parallele logische
Sprache. 1995. Diploma Thesis. Dresden University of Technology. (in
german).
|
|
|
|