«DF : a Feature Constraint System
and the Language Concurrent Extension»
Liviu-Virgil Ciortuz (DFKI, Saarbruck)
Abstract - This paper presents a feature constraint system that, compared with the well-known systems OSF[1] and CFT[6], incorporates several interesting characteristics. The new system, called DF, is naturally extended through the CLP scheme (in combination with a dynamic completion technique) to a logic language equally called DF. The DF feature constraint system adopted the F-logic's [5] declarative semantics, and the DF language successfully puts F-logic to work in a concurrent-flavoured manner, with a completely rebuilt operational semantics. Concurrency came into DF by
- acceptation of partially specified (``open'') sort hierarchies,
- object-oriented principle-based completion of sort hierarchies,
- automate suspension upon unification failure and reactive resumption on local completion of the sort hierarchy,
- interleaving DF logic goal solving with conditional unification of DF logic records,
- on-demand parallel-like solving of DF logic goals, supported by the concurrent (Oz) implementation background.
«Une alternative efficace au backtrack chronologique pour les
recherches arborescentes - Application au problème d'Open-Shop»
Narendra Jussien et Christelle Guéret (Ecole des Mines de Nantes)
Résumé - La plupart des recherches arborescentes utilisent un backtrack chronologique, ce qui n'est pas très efficace. Nous proposons une technique de backtrack intelligent permettant d'accélérer la recherche de solutions. Cette technique est une adaptation de nos précédents travaux sur un système générique d'explications pour la programmation par contraintes [Jussien et Boizumault, 1997]. Très peu de recherches arborescentes ont été développées pour le problème d'Open-Shop. Certains problèmes carrés de taille 7 sont encore ouverts. Nous avons donc adapté notre approche à la meilleure recherche arborescente à notre connaissance pour l'Open-Shop, méthode proposée dans [Brucker et al., 1997]. Les améliorations obtenues sur des problèmes de la littérature (proposés dans [Taillard, 1993]) sont très intéressantes. Nous résolvons entre autre un problème carré ouvert de taille 10.
«Représentation de séquences définies sur des ensembles non instanciés
par arbre PQR partiel»
Lotfi Berkaoui et Bruno Legeard (Laboratoire d'Informatique de Besançon)
Résumé - Dans des articles précédents, nous avons montré l'apport d'hypergraphe d'intervalles ordonnés, appelé arbre PQR, pour la représentation de contraintes caractérisant des ensembles partiellement ordonnés appelés séquences. Les contraintes s'exprimant sur des ensembles clos à partir de relations de précédence, de groupe et de rang. L'arbre PQR permet une représentation canonique de l'ensemble des séquences admissibles relativement à un système de contraintes, associé à un test pôlynomial de consistance. Dans cet article, nous proposons une nouvelle structure arborescente, appelée arbre PQR Partiel, permettant une représentation canonique de séquences définies sur des structures ensemblistes non nécessairement instanciées. Cette représentation assure, d'une part une flexibilité au niveau de la définition de la séquence, en ce sens où l'ensemble de référence peut être partiellement ou totalement inconnu et d'autre part, une construction incrémentale de la collection finale d'objets à séquencer. Une fois construit, l'arbre PQR Partiel initial sera progressivement transformé lors de la pose des contraintes. Cette technique assure une construction simultanée de la séquence et de son ensemble de référence en propageant les contraintes relatives à une structure sur la deuxième.
Mots clés - programmation logique, contraintes ensemblistes, séquences, arbre PQR Partiel.