The Marseille Constraint based Configuration Group
The web resource of the Configuration Team, member of the InCA Team, from the LSIS Laboratory, Marseille, France
Constraint Based Configuration
Publications
LSIS
CNRS
Université de la Méditerranée
Université Paul CézannePeople
Laurent Henocque (Associate Pr.)
Nicolas Prcovic (Assistant Pr.)
Mathieu Estratat (Post doc.)
Mathias Kleiner (Doctor)
and formerly
Stephane Grandcolas (Assistant Pr.)
Related Links
Associations
the Association Française pour la Programmation par Contraintes
CP Online, the web site of the ACP
Configuration tool providers
Z
Semantic Web
(note: as a group rule, author names are alphabetically sorted in all publications)
Publications
-
Incomplete search
- , "Ant Colony Optimisation for Configuration", in: Proceedings of the 20th IEEE Intl Conference on Tools with Artificial Intelligence, ICTAI'08, pp. to appear, Dayton, OHIO, USA, November, 2008. [pdf] (abstract) (bibtex)
abstract
An inherent difficulty in enumerative search algo- rithms for optimisation is the combinatorial explosion that occurs when increasing the size of the input. Among incomplete algorithms that address this issue, Ant Colony Optimization (ACO) uses à combination of random and heuristic methods plus reinforcement lear- ning, which proved efficient on à wide range of CSPs problems. This paper presents early results in applying an ACO-based algorithm to configuration, which to the best of our knowledge was never investigated before. We describe how the nature of unbounded configura- tion problems impacts the ACO approach due to the presence of set-variables with open domains. We pro- pose an ACO framework able to deal with those issues through an original pheromone model and algorithm. We also present the use of Par ticle Swarm Optimiza- tion (PSO) to converge towards good parameter sets. Finally, we provide expérimental results, both for ran- dom problem instances and the 'racks' optimisation problem.bibtex
@inproceedings {2008AlbertHenocqueKleiner-ICTAIACO,
author = {Patrick Albert, Laurent Henocque, Mathias Kleiner},
title = {Ant Colony Optimisation for Configuration},
booktitle = {Proceedings of the 20th IEEE Intl Conference on Tools with Artificial Intelligence, ICTAI'08},
pages = {to appear},
address = {Dayton, OHIO, USA},
month = {November},
year = {2008}},
} - , "Ant Colony Optimisation for Constraint-based Configuration", in: Proceedings of the International Conference on Metaheuristics and Nature Inspired Computing, META'08, pp. 1--10, Hammamet, Tunisia, October, 2008. [pdf] (abstract) (bibtex)
abstract
An inherent difficulty in enumerative search algo- rithms for optimisation is the combinatorial explosion that occurs when increasing the size of the input. Among incomplete algorithms that address this issue, Ant Colony Optimization (ACO) uses à combination of random and heuristic methods plus reinforcement lear- ning, which proved efficient on à wide range of CSPs problems. This paper presents early results in applying an ACO-based algorithm to configuration, which to the best of our knowledge was never investigated before. We describe how the nature of unbounded configura- tion problems impacts the ACO approach due to the presence of set-variables with open domains. We pro- pose an ACO framework able to deal with those issues through an original pheromone model and algorithm. We also present the use of Par ticle Swarm Optimiza- tion (PSO) to converge towards good parameter sets. Finally, we provide expérimental results, both for ran- dom problem instances and the 'racks' optimisation problem.bibtex
@inproceedings {2008AlbertHenocqueKleiner-JFPC,
author = {Patrick Albert, Laurent Henocque, Mathias Kleiner},
title = {Ant Colony Optimisation for Constraint-based Configuration},
booktitle = {Proceedings of the International Conference on Metaheuristics and Nature Inspired Computing, META'08},
pages = {1--10},
address = {Hammamet, Tunisia},
month = {October},
year = {2008}},
} - , "Optimisation par colonie de fourmis pour la configuration", in: Proceedings of the quatrièmes journées Francophones de Programmation par Contraintes, JFPC'08, pp. 1--10, Nantes, France, Juin, 2008. [pdf] (abstract) (bibtex)
abstract
An inherent difficulty in enumerative search algo- rithms for optimisation is the combinatorial explosion that occurs when increasing the size of the input. Among incomplete algorithms that address this issue, Ant Colony Optimization (ACO) uses à combination of random and heuristic methods plus reinforcement lear- ning, which proved efficient on à wide range of CSPs problems. This paper presents early results in applying an ACO-based algorithm to configuration, which to the best of our knowledge was never investigated before. We describe how the nature of unbounded configura- tion problems impacts the ACO approach due to the presence of set-variables with open domains. We pro- pose an ACO framework able to deal with those issues through an original pheromone model and algorithm. We also present the use of Par ticle Swarm Optimiza- tion (PSO) to converge towards good parameter sets. Finally, we provide expérimental results, both for ran- dom problem instances and the 'racks' optimisation problem.bibtex
@inproceedings {2008AlbertHenocqueKleiner-JFPC,
author = {Patrick Albert, Laurent Henocque, Mathias Kleiner},
title = {Optimisation par colonie de fourmis pour la configuration},
booktitle = {Proceedings of the quatri\`{e}mes journ\'{e}es Francophones de Programmation par Contraintes, JFPC'08},
pages = {1--10},
address = {Nantes, France},
month = {Juin},
year = {2008}},
}
- , "Ant Colony Optimisation for Configuration", in: Proceedings of the 20th IEEE Intl Conference on Tools with Artificial Intelligence, ICTAI'08, pp. to appear, Dayton, OHIO, USA, November, 2008. [pdf] (abstract) (bibtex)
-
Semantic Web
- , "An end-to-end configuration-based framework for automatic SWS composition", in: Proceedings of the 20th IEEE Intl Conference on Tools with Artificial Intelligence, ICTAI'08, pp. to appear, Dayton, OHIO, USA, November, 2008. [pdf] (abstract) (bibtex)
abstract
Semantic Web Service (SWS) composition is a challenging AI problem. We describe a theoretical and experimental framework based upon finite model search for constrained object models to address this problem. In many AI situations the input is rather simple, and the results complex to obtain. SWS composition requests themselves can turn very complex, and the problem of building these requests can be viewed as an AI problem of its own. This paper presents an operational end to end approach to composing/publishing Semantic Web Services involving two main reasoning stages. Composing is first performed at the abstract level of goals (each roughly representing a discovery request), which yields a composition request at the workflow level. The resulting worklow is finally processed to generate a valid publishable semantic web service. We present experimental results obtained on industrial use cases during the DIP project.from specific solving tools.bibtex
@inproceedings {2008AlbertHenocqueKleiner-ICTAISWS,
author = {Patrick Albert, Laurent Henocque, Mathias Kleiner},
title = {An end-to-end configuration-based framework for automatic SWS composition},
booktitle = {Proceedings of the 20th IEEE Intl Conference on Tools with Artificial Intelligence, ICTAI'08},
pages = {to appear},
address = {Dayton, OHIO, USA},
month = {November},
year = {2008}},
} - , "3-Level Behavioural Models for Semantic Web Services", Journal of Multi-agent and Grid Systems (MAGS), pp. to appear, Amsterdam, The Netherlands, 2008. (abstract) (bibtex)
abstract
There are two types of behavioural models in the WSMO semantic description of services: an orchestration and a choreography, together called the interface. While an orchestration defines a service's behaviour as a composition of existing parts, a choreography is intended to document the conversation of messages exchanged with its client. This paper presents a three-level model for behavioural descriptions, and how UML Activity Diagrams and the Cashew workflow model fit into this, building on existing work on the use of Abstract State Machines to define behaviour in WSMO. A choreography is also associated with a goal in WSMO, not simply as a reversal of the message exchange roles: the messages themselves may be described in different ontologies, requiring data mediation, and the exchange pattern may be different, requiring process mediation. An orchestration, on the other hand, considers more parties than the client, since it describes how the behaviour of a service is composed from serveral parts. In general this may involve both web services and goals, allowing the resolution of goals to services, via discovery, to be deferred until run-bibtex
@article {NortonPedrinacciHenocqueKleiner06mags,
author = {Barry Norton, Carlos Pedrinacci, Laurent Henocque, Mathias Kleiner},
title = {3-Level Behavioural Models for Semantic Web Services},
journal = {Journal of Multi-agent and Grid Systems (MAGS)},
pages = {to appear},
address = {Amsterdam, The Netherlands},
year = {2008}},
} - , "Contribution to the use of Constraint Programming for
Finite Model Search in Artificial Intelligence", in: Thèse de Doctorat de l'Université de la Méditerranée-Aix-Marseille II, pp. 1--206, Marseille, France, Novembre, 2007. [pdf] (abstract) (bibtex)
abstract
This thesis aims at using constraint programming, and more precisely finite model search for constraint ob ject models, to achieve symbolic reasoning and address artificial intelligence prob- lems. A the denotational level, we illustrate the expressive power of the chosen formalism through the description of a theoretical and experimental framework addressing a very modern challenge: the automatic composition of semantic web services. This framework, developped during the DIP European pro ject and prototyped using ILOG’s tool JConfigurator, has been integrated in the pro ject’s architecture and tested on industrial use cases. At the operational level, we describe algorithms dealing with the inherent combinatorial explo- sion of enumerative methods. We propose a pseudo-linear time algorithm that approximates colored directed acyclic graphs canonicity detection, allowing early backtrack when generating isomorphic configurations during the search. The theoretical results are backed by a range of experiments. We also propose a stochastic method based on simulated ant colony behaviour which handles original first-order logic issues. There again we present experimental results.bibtex
@phdthesis {Kleiner07PHD,
author = {Mathias Kleiner},
title = {Contribution to the use of Constraint Programming for Finite Model Search in Artificial Intelligence},
booktitle = {Th\`{e}se de Doctorat de l'Universit\'{e} de la M\'{e}diterran\'{e}e-Aix-Marseille II},
type = {Th\`{e}se de doctorat},
school = {Universit\'{e} de la M\'{e}diterran\'{e}e-Aix-Marseille II},
pages = {1--206},
address = {Marseille, France},
month = {Novembre},
year = {2007}},
} - , "Configuring Configuration Requests: An Application to the Semantic Web", in: proceedings twenty-second Conference on Artificial Intelligence (AAAI-07) Configuration Workshop, pp. 1--6, Vancouver, British Columbia, Canada, July, 2007. [pdf] (abstract) (bibtex) link
abstract
Beyond its usual industrial fields of application, a current body of research explores the use of constraint based con- figuration to address general AI problems, like for instance automatic composition of semantically enriched web services (SWS). A configuration request is naturally formulated as a fragment of the desired solution, that the configurator will at- tempt to complete according to constraints. We address here a case where the design of the configuration request may itself be the result of a configuration phase, that helps the user de- sign the request by formulating it on more abstract grounds. Within this framework, the configurator is first used to com- plete an abstract request formulated in a specific formalism. Then a translation is performed from the goal model to the final model to yield the actual request sent to the second con- figuration phase. This research builds on previous experi- ence showing the adequacy of using configuration to com- pose SWS, that raised further issues regarding the nature of queries.bibtex
@inproceedings {2007HenocqueKleiner-AAAIConfiguration,
author = {Laurent Henocque, Mathias Kleiner},
title = {Configuring Configuration Requests: An Application to the Semantic Web},
booktitle = {proceedings twenty-second Conference on Artificial Intelligence (AAAI-07) Configuration Workshop},
pages = {1--6},
address = {Vancouver, British Columbia, Canada},
month = {July},
year = {2007}},
} - , "Composition", in: Semantic Web Services : Concepts, technologies, and applications, edited by Rudi Studer, Stephan Grimm, Andreas Abecker, publisher: Springer-Verlag Berlin and Heidelberg GmbH and Co. KG, pp. 245--286, Marseille, France, 2007. (abstract) (bibtex)
abstract
Composition is a main challenge for the Semantic Web Ser- vices (SWS) community. Among existing approaches, it was shown ef- ficient to use constraint based configuration to create composite SWS orchestrations out of elementary SWS choreographies. Further experi- ments have revealed the limitations and semantic ambiguities that arise from over-simplistic composition requests. The present paper analyzes those issues, presents the requirements and specification for an extended composition request language addressing them, and details how to auto- matically generate the implied constraints for a configuration based com- poser. The whole approach has been experimentally validated with use case partners using a configuration based composition prototype within the DIP pro ject.bibtex
@book {2007HenocqueKleiner-SWSBook,
author = {Laurent Henocque, Mathias Kleiner},
title = {Composition},
booktitle = {Semantic Web Services : Concepts, technologies, and applications},
editor = {Rudi Studer, Stephan Grimm, Andreas Abecker},
publisher = {Springer-Verlag Berlin and Heidelberg GmbH and Co. KG},
pages = {245--286},
address = {Marseille, France},
year = {2007}},
isbn = {3540708936},
} - , "A constrained request language for SWS Composition", in: LSIS Research Report 2007, institute: LSIS-UMR6168-Marseille, pp. 1--15, Marseille, France, 2007. [pdf] (abstract) (bibtex)
abstract
Composition is a main challenge for the Semantic Web Ser- vices (SWS) community. Among existing approaches, it was shown ef- ficient to use constraint based configuration to create composite SWS orchestrations out of elementary SWS choreographies. Further experi- ments have revealed the limitations and semantic ambiguities that arise from over-simplistic composition requests. The present paper analyzes those issues, presents the requirements and specification for an extended composition request language addressing them, and details how to auto- matically generate the implied constraints for a configuration based com- poser. The whole approach has been experimentally validated with use case partners using a configuration based composition prototype within the DIP pro ject.bibtex
@techreport {HenocqueKleiner07crl-researchreport,
author = {Laurent Henocque, Mathias Kleiner},
title = {A constrained request language for SWS Composition},
booktitle = {LSIS Research Report 2007},
institution = {LSIS-UMR6168-Marseille},
pages = {1--15},
address = {Marseille, France},
year = {2007}},
} - , "Language de Requête Configurable pour la Composition de Services Web Semantiques - article jeune chercheur", in: Proceedings of the deuxièmes journées Francophones de Programmation par Contraintes, JFPC'06, pp. 369--378, Nîmes, France, Juin, 2006. [pdf] (abstract) (bibtex)
abstract
Composition is a main challenge for the Semantic Web Services (SWS) community. Among existing ap- proaches, it was shown efficient to use constraint based technics (as configuration) to create orchestrations out of choreographies. Further experiments have revealed issues on the semantic ambiguities and limitations that could raise from the requests made to a composer. The present paper presents an original approach where the request is seen as a problem in itself, and shows how configuration can be used to solve it using a given con- strained object model.bibtex
@inproceedings {2006HenocqueKleiner-JFPC,
author = {Patrick Albert, Laurent Henocque, Mathias Kleiner},
title = {Language de Requête Configurable pour la Composition de Services Web Semantiques - article jeune chercheur},
booktitle = {Proceedings of the deuxi\`{e}mes journ\'{e}es Francophones de Programmation par Contraintes, JFPC'06},
pages = {369--378},
address = {N\^{i}mes, France},
month = {Juin},
year = {2006}},
} - , "Composition de Workflows à l’aide de la Configuration", in: Proceedings of the premières journées Francophones de Programmation par Contraintes, JFPC'05, pp. 345--354, Lens, France, Juin, 2005. [pdf] (abstract) (bibtex)
abstract
La composition automatique ou assistée de workflows est un domaine d'intense recherche avec des applications au 'world wide web' et à la modélisation de processus métiers (BPM), traditionnellement envisagée en utilisant des techniques de programmation logique et de démonstration automatique. L'originialité de cette recherche provient de l'observation que la construction d'un workflow composite est un problème de recherche de modèles finis, et que la plupart des languages de workflows peuvent être définis par des métamodèles objets contraints, comme UML ou YAWL. Cela conduit à envisager l'application de techniques de configuration à base de contraintes à ce problème, ce dont nous montrons la faisabilité. Nous présentons un modèle objet contraint pour la composition de workflows, s'appuyant sur un métamodèle contraint ainsi que des ontologies de processus et de flots de données. Des résultats expérimentaux sont donnés pour une implantation qui génère des workflows composites complexes mettant en jeu transformations, synchronisations et tests.bibtex
@inproceedings {2005AlbertHenocqueKleiner-JFPC,
author = {Patrick Albert, Laurent Henocque, Mathias Kleiner},
title = {Composition de Workflows \`{a} l’aide de la Configuration},
booktitle = {Proceedings of the premi\`{e}res journ\'{e}es Francophones de Programmation par Contraintes, JFPC'05},
pages = {345--354},
address = {Lens, France},
month = {Juin},
year = {2005}},
} - , "Configuration Based Workflow Composition", in: Proceedings of the IEEE International Conference on Web Services (ICWS'05), pp. 285--292, Orlando, Florida, USA, July, 2005. [pdf] (abstract) (bibtex)
abstract
Automatic or assisted workflow composition is a field of intense research for applications to the world wide web or to business process modeling. Workflow composition is traditionally addressed in various ways, generally via theorem proving techniques. The originality of this research stems from the observation that building a composite workflow bears strong relationships with finite model search, and that some workflow languages can be defined as constrained object metamodels [1], [2]. This leads to consider the viability of applying configuration techniques to this problem. Our main contribution is to prove the feasibility of such an approach, with some advantages and drawbacks compared to logical based techniques. We present a constrained object model for workflow compo- sition, based upon a metamodel for workflows and ontologies for processes and data flows. Experimental results are listed for a working implementation that generates complex interleaving composite workflows involving transformations, synchronization and branching constructs.bibtex
@inproceedings {KleinerHenocque05icws,
author = {Patrick Albert, Laurent Henocque, Mathias Kleiner},
title = {Configuration Based Workflow Composition},
booktitle = {Proceedings of the IEEE International Conference on Web Services (ICWS'05)},
pages = {285--292},
address = {Orlando, Florida, USA},
month = {July},
year = {2005}},
} - , "A Constrained Object Model for Configuration Based Workflow Composition", in: Revised and Selected Papers, Business Process Management - BPM 2005 Workshops, edited by Bussler C. et Al, publisher: Springer, series: Lecture Notes in Computer Science, volume 3812, pp. 102--115, Nancy, France, January, 2006. [pdf] (abstract) (bibtex)
abstract
Automatic or assisted workflow composition is a field of in- tense research for applications to the world wide web or to business pro- cess modeling. Workflow composition is traditionally addressed in various ways, generally via theorem proving techniques. Recent research [1] ob- served that building a composite workflow bears strong relationships with finite model search, and that some workflow languages can be defined as constrained ob ject metamodels [2, 3]. This lead to consider the viability of applying configuration techniques to this problem, which was proven feasible. Constrained based configuration expects a constrained ob ject model as input. The purpose of this document is to formally specify the constrained ob ject model involved in ongoing experiments and research using the Z specification language.bibtex
@inproceedings {AlbertHenocqueKleiner05BPMChorOrchWorkshopRevised,
author = {Patrick Albert, Laurent Henocque, Mathias Kleiner},
title = {A Constrained Object Model for Configuration Based Workflow Composition},
booktitle = {Revised and Selected Papers, Business Process Management - BPM 2005 Workshops},
editor = {Bussler C. et Al},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {3812},
pages = {102--115},
address = {Nancy, France},
month = {January},
year = {2006}},
} - , "A Constrained Object Model for Configuration Based Workflow Composition", in: Proceedings of the 1st International Workshop on Web Service Choreography and Orchestration for Business Process Management, BPM'05, pp. (no pages), Nancy, France, 2005. (abstract) (bibtex)
abstract
Automatic or assisted workflow composition is a field of in- tense research for applications to the world wide web or to business pro- cess modeling. Workflow composition is traditionally addressed in various ways, generally via theorem proving techniques. Recent research [1] ob- served that building a composite workflow bears strong relationships with finite model search, and that some workflow languages can be defined as constrained ob ject metamodels [2, 3]. This lead to consider the viability of applying configuration techniques to this problem, which was proven feasible. Constrained based configuration expects a constrained ob ject model as input. The purpose of this document is to formally specify the constrained ob ject model involved in ongoing experiments and research using the Z specification language.bibtex
@inproceedings {AlbertHenocqueKleiner05BPMChorOrchWorkshop,
author = {Patrick Albert, Laurent Henocque, Mathias Kleiner},
title = {A Constrained Object Model for Configuration Based Workflow Composition},
booktitle = {Proceedings of the 1st International Workshop on Web Service Choreography and Orchestration for Business Process Management, BPM'05},
pages = {(no pages)},
address = {Nancy, France},
year = {2005}},
} - , "A Constrained ObjectModel for Configuration Based WorkflowC omposition", in: Arxiv Research Report 0506031, institute: LSIS UMR CNRS 6168, pp. 1--19, Marseille, France, 2005. [pdf] (abstract) (bibtex)
abstract
Automatic or assisted workflow composition is a field of intense research for applications to the world wide web or to business process modeling. Workflow composition is traditionally addressed in various ways, generally via theorem proving techniques. The originality of this research stems from the observation that building a composite workflow bears strong relationships with finite model search, and that some workflow languages can be defined as constrained object metamodels [1], [2]. This leads to consider the viability of applying configuration techniques to this problem. Our main contribution is to prove the feasibility of such an approach, with some advantages and drawbacks compared to logical based techniques. We present a constrained object model for workflow compo- sition, based upon a metamodel for workflows and ontologies for processes and data flows. Experimental results are listed for a working implementation that generates complex interleaving composite workflows involving transformations, synchronization and branching constructs.bibtex
@techreport {AlbertHenocqueKleiner05arxiv050631,
author = {Patrick Albert, Laurent Henocque, Mathias Kleiner},
title = {A Constrained ObjectModel for Configuration Based WorkflowC omposition},
booktitle = {Arxiv Research Report 0506031},
institution = {LSIS UMR CNRS 6168},
pages = {1--19},
address = {Marseille, France},
year = {2005}},
}
- , "An end-to-end configuration-based framework for automatic SWS composition", in: Proceedings of the 20th IEEE Intl Conference on Tools with Artificial Intelligence, ICTAI'08, pp. to appear, Dayton, OHIO, USA, November, 2008. [pdf] (abstract) (bibtex)
-
Symmetry - Isomorphisms
- , "Handling Configuration Isomorphisms - Extended research report", pp. 1--37, July, 2008. [pdf] (abstract) (bibtex)
abstract
An inherent difficulty in solving configuration problems is the existence of many structural isomorphisms. This issue of considerable importance attracted little research interest despite its broad applicability to configuration. We address the problem at two levels. We first present a definition of canonicity for configuration trees and an enumeration algorithm that can be used for configuration problems involving solely composition constraints. The main result is that the algorithm can backtrack as soon as a non canonical tree is constructed. We then extend the properties and algorithms to the general configuration case, where configuration results are directed acyclic graphs. There again, testing (weak) canonicity remains polynomial, and significantly impacts the behavior of enumeration. We provide theoretical and experimental results on a range of problems. This paper was submitted to the Constraints Journal special issue on Symmetry 2008.bibtex
@techreport {2008GrancolasHenocqueKleinerPrcovic-RR,
author = {Stephane Grandcolas, Laurent Henocque, Mathias Kleiner, Nicolas Prcovic},
title = {Handling Configuration Isomorphisms - Extended research report},
pages = {1--37},
month = {July},
year = {2008}},
} - , "Génération rapide et filtrage de configurations canoniques", in: proceedings des troisièmes journées Francophones de Programmation par Contraintes, JFPC'07, pp. 357--366, Rocquencourt, France, Juin, 2007. [pdf] (abstract) (bibtex) link
abstract
La configuration sous contraintes présente une nouvelle difficulté à prendre en compte par les méthodes d'élimination de symétries connues par la communauté CSP car elle y introduit un aspect dynamique. Nous présentons ici une amélioration significative d'un algorithme de génération de configurations canoniques. Cette nouvelle version exploite l'incrémentalité que l'on peut faire ressortir de la génération de solutions canoniques et de l'ordre total sur les arbres sur laquelle elle repose. La complexité du test de canonicité passe ainsi de O(Nlog(N)) à O(N). De plus, une technique de filtrage nous permet d'éliminer à l'avance des configurations non canoniques. Des résultats expérimentaux montrent l'intérêt de cette approche sur des problèmes classiques.bibtex
@inproceedings {2007HenocqueKleiner-JFPC,
author = {Laurent Henocque, Nicolas Prcovic},
title = {G\'{e}n\'{e}ration rapide et filtrage de configurations canoniques},
booktitle = {proceedings des troisi\`{e}mes journ\'{e}es Francophones de Programmation par Contraintes, JFPC'07},
pages = {357--366},
address = {Rocquencourt, France},
month = {Juin},
year = {2007}},
} - , "Fast Canonical Configuration Generation and Filtering", in: proceedings twenty-second Conference on Artificial Intelligence (AAAI-07) Configuration Workshop, pp. 1--6, Vancouver, British Columbia, Canada, July, 2007. [pdf] (abstract) (bibtex) link
abstract
Constraint based configuration challenges symmetry elimina- tion methods known to the constraint solving community by introducing dynamics. We present here a significant improve- ment of an algorithm for generating canonical configurations. The new version fully exploits the incremental generation of canonical solutions both at the level of the canonicity test and in the tree ordering function, which turns the cost of canon- icity testing down from O(Nlog(N)) to O(N). Filtering addi- tionally provides the possibility to proactively discard fail- ure situations. Experimental results provide evidence of the significance of this approach, on test problems and known benchmarks. plied to canonical enumeration.bibtex
@inproceedings {2007HenocquePrcovic-AAAIConfiguration,
author = {Laurent Henocque, Nicolas Prcovic},
title = {Fast Canonical Configuration Generation and Filtering},
booktitle = {proceedings twenty-second Conference on Artificial Intelligence (AAAI-07) Configuration Workshop},
pages = {1--6},
address = {Vancouver, British Columbia, Canada},
month = {July},
year = {2007}},
} - , "Handling Configuration Isomorphisms", in: LSIS Research Report 2006, submitted to Constraint Journal - Special Issues on Symmetries, institute: LSIS-UMR6168-Marseille, pp. 1--29, Marseille, France, 2006. [pdf] (abstract) (bibtex)
abstract
An inherent difficulty in solving configuration problems is the exis- tence of many structural isomorphisms. This issue of considerable importance at- tracted little research interest despite its broad applicability to configuration. We address the problem at two levels. We first present a definition of canonicity for configuration trees and an enumeration algorithm that can be used for configura- tion problems involving solely composition constraints. The main result is that the algorithm can backtrack as soon as a non canonical tree is constructed. We then extend the properties and algorithms to the general configuration case, where con- figuration results are directed acyclic graphs. There again, testing (weak) canon- icity remains polynomial, and significantly impacts the behavior of enumeration. We provide theoretical and experimental results on a range of problems.bibtex
@techreport {HenocqueKleiner07crl-researchreport,
author = {St\'{e}phane Grandcolas, Laurent Henocque, Mathias Kleiner, Nicolas Prcovic},
title = {Handling Configuration Isomorphisms},
booktitle = {LSIS Research Report 2006},
journal = {submitted to Constraint Journal - Special Issues on Symmetries},
institution = {LSIS-UMR6168-Marseille},
pages = {1--29},
address = {Marseille, France},
year = {2006}},
} - , "Une procédure générale d'élimination d'isomorphismes pour les problèmes de configuration", in: Proceedings of the Premières Journées Francophones de Programmation par Contraintes, JFPC'2005, pp. 335-344, Lens, France, Juin, 2005. [pdf] [ps] (abstract) (bibtex)
abstract
An inherent difficulty in solving configuration problems is the existence of many structural isomorphisms. We define two search procedures allowing the removal of large portions of the search space that provably contai solely non canonical solutions. The tests performed on each node are time polynomial. Experimental results are reported on a simple yet realistic configuration example.bibtex
@inproceedings {2005HenocqueKleinerPrcovic-JFPC,
author = {Laurent Henocque, Mathias Kleiner, Nicolas Prcovic},
title = {Une proc\'{e}dure g\'{e}n\'{e}rale d'\'{e}limination d'isomorphismes pour les probl\`{e}mes de configuration},
booktitle = {Proceedings of the Premi\`{e}res Journ\'{e}es Francophones de Programmation par Contraintes, JFPC'2005},
pages = {335-344},
address = {Lens, France},
month = {Juin},
year = {2005}},
} - , "Advances in Polytime Isomorph Elimination for Configuration", in: proceedings of Principles and Practice of Constraint Programming - CP 2005, publisher: Springer Berlin / Heidelberg, series: Lecture Notes in Computer Science, volume 3709, pp. 301--313, Sitges Barcelona, Spain, 2005. [pdf] (abstract) (bibtex) link
abstract
An inherent and often very underestimated difficulty in solving configuration problems is the existence of many structural isomorphisms. This issue of considerable importance attracted little research interest despite its applicability to almost all configuration problems. We define two search procedures allowing the removal of large portions of the search space that provably solely contain non canonical solutions. The tests performed on each node are time polynomial. Experimental results are reported on a simple generic configuration example.bibtex
@inproceedings {2005HenocqueKleinerPrcovic-JFPC,
author = {Laurent Henocque, Mathias Kleiner, Nicolas Prcovic},
title = {Advances in Polytime Isomorph Elimination for Configuration},
booktitle = {proceedings of Principles and Practice of Constraint Programming - CP 2005},
publisher = {Springer Berlin / Heidelberg},
series = {Lecture Notes in Computer Science},
volume = {3709},
pages = {301--313},
address = {Sitges Barcelona, Spain},
year = {2005}},
isbn = {978-3-540-29238-8},
} - , "Practically Handling Configuration Automorphisms", in: proceedings of ICTAI 2004, the 16th IEEE International Conference on Tools for Artificial Intelligence, pp. 90-97, Boca Raton, Florida USA, November 15-17, 2004. [pdf] (abstract) (bibtex) link
abstract
Configuring consists in simulating the realization of a complex product from a catalog of component parts, using known relations between types, and picking values for ob- ject attributes. A configuration can be viewed as a graph of interconnected components. An inherent difficulty in solv- ing configuration problems is the existence of many struc- tural isomorphisms. A practical way of dealing with iso- morphisms is by isolating one configuration in each equiv- alence class called a canonical representative. Since no polytime algorithm is known for the general graph isomor- phism problem, it is interesting to explore sub-problems that can efficiently be exploited by backtrack search pro- cedures. We describe a formalism independent approach to detect a large number of structure related configura- tion isomorphisms. The algorithm has the essential prop- erty that isomorphism detection is both incremental and can be performed in pseudo linear time, two essential con- ditions for backtrack search. Backtrack occurs as soon as a non weakly canonical DAG structure is generated for a configuration, which allows to extend the range of practi- cally tractable problems, as shown experimentally. Weakly canonical configurations explicitly expose their automor- phism group, which is readily available thanks to the lex- icographic ordering chosen. The efficiency of the approach is assessed both theoretically and by experimental results obtained for a range of realistic configuration problems.bibtex
@article {2004GrandcolasHenocquePrcovic-ICTAI,
author = {Laurent Henocque, Nicolas Prcovic},
title = {Practically Handling Configuration Automorphisms},
booktitle = {proceedings of ICTAI 2004, the 16th IEEE International Conference on Tools for Artificial Intelligence},
pages = {90-97},
address = {Boca Raton, Florida USA},
month = {November 15-17},
year = {2004}},
} - , "Un test de canonicité pour éliminer des configurations redondantes", Journal Electronique d'Intelligence Artificielle (JEDAI), edited by Jérôme Lang, Pierre Marquis, Thomas Schiex, volume 3, pp. 1--16, Marseille, France, 2004. [pdf] (abstract) (bibtex)
abstract
Configurer consiste à simuler la réalisation d'un produit complexe à partir de composants choisis dans un catalogue de types, en s'appuyant sur les relations connues entre ces types, et en instanciant leurs attributs. C'est un problème combinatoire relevant de la programmation par contraintes, ayant fait l'objet de nombreuses approches différentes depuis le système R1. Une difficulté inhérente aux problèmes de configuration est l'existence de nombreux isomorphismes entre les interprétations. Nous décrivons une approche pour étendre de façon signicative les isomorphismes reconnus par les configurateurs, indépendamment du formalisme choisi, et sans nécessiter de modifier le modèle. Nous exploitons pour cela les propriétés d'un fragment reconnaissable de tout problème de configuration, le sous-problème structurel, dont les solutions canoniques peuvent être produites à coût réduit, pour des bénéfices considérables. Nous décrivons un algorithme pour le test de canonicité des configurations, pouvant être décliné comme une contrainte, dont nous donnons la complexité et le pouvoir de coupure.bibtex
@article {2004GrandcolasHenocquePrcovic-JEDAI,
author = {Stephane Grandcolas, Laurent Henocque, Nicolas Prcovic},
title = {Un test de canonicit\'{e} pour \'{e}liminer des configurations redondantes},
journal = {Journal Electronique d'Intelligence Artificielle (JEDAI)},
editor = {J\'{e}rôme Lang, Pierre Marquis, Thomas Schiex},
volume = {3},
pages = {1--16},
address = {Marseille, France},
year = {2004}},
} - , "Traitement pratique des isomorphismes dans les problèmes de configuration", in: proceedings of the 10 ièmes journées Nationales sur la résolution pratique des problèmes NP-complets, JNPC'04, pp. 187--202, Angers, France, Juin, 2004. [pdf] (abstract) (bibtex) link
abstract
Configurer consiste à simuler la réalisation d'un produit complexe à partir de composants choisis dans un catalogue de types, en s'appuyant sur les relations connues entre ces types et en instanciant leurs attributs. Une difficulté inhérente aux problèmes de configuration est l'existence de nombreux isomorphismes structurels. Nous décrivons une approche pour étendre de façon signicative les isomorphismes reconnus par les configurateurs indépendamment du formalisme choisi et sans nécessiter de modifier le modèle. Grâce à une procédure permettant de n'accepter que des structures sous forme de DAG dits faiblement canoniques, ces isomorphismes peuvent être traités à un coût réduit de manière à ce qu'une partie considérable des solutions non canoniques soit écartées. De plus, les automorphismes des structures produites sont automatiquement donnés par cette même procédure et peuvent servir à traiter les symétries restantes. Cette approche offre un avantage évident par rapport à la détection d'automorphismes basés sur des algorithmes généraux de calcul de groupes de permutations. L'efficacité théorique de notre approche est vérifiée par des résultats expérimentaux qui réduisent les temps de calculs de solutions de telle sorte que la taille des problèmes traitables en pratique se trouve considérablement augmentée.bibtex
@inproceedings {EstratatHenocque04jnpc,
author = {Laurent Henocque, Nicolas Prcovic},
title = {Traitement pratique des isomorphismes dans les probl\`{e}mes de configuration},
booktitle = {proceedings of the 10 i\`{e}mes journ\'{e}es Nationales sur la r\'{e}solution pratique des probl\`{e}mes NP-complets, JNPC'04},
pages = {187--202},
address = {Angers, France},
month = {Juin},
year = {2004}},
} - , "A Canonicity Test for Configuration", in: proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP-2003), pp. 853-857, Kinsale, County Cork, Ireland , September, 2003. (abstract) (bibtex) link
abstract
Configuring consists in simulating the realization of a complex product from a catalog of component parts, using known relations between types, and picking values for ob- ject attributes. A configuration can be viewed as a graph of interconnected components. An inherent difficulty in solv- ing configuration problems is the existence of many struc- tural isomorphisms. A practical way of dealing with iso- morphisms is by isolating one configuration in each equiv- alence class called a canonical representative. Since no polytime algorithm is known for the general graph isomor- phism problem, it is interesting to explore sub-problems that can efficiently be exploited by backtrack search pro- cedures. We describe a formalism independent approach to detect a large number of structure related configura- tion isomorphisms. The algorithm has the essential prop- erty that isomorphism detection is both incremental and can be performed in pseudo linear time, two essential con- ditions for backtrack search. Backtrack occurs as soon as a non weakly canonical DAG structure is generated for a configuration, which allows to extend the range of practi- cally tractable problems, as shown experimentally. Weakly canonical configurations explicitly expose their automor- phism group, which is readily available thanks to the lex- icographic ordering chosen. The efficiency of the approach is assessed both theoretically and by experimental results obtained for a range of realistic configuration problems.bibtex
@article {2003GrandcolasHenocquePrcovic-CP,
author = {Stephane Grandcolas, Laurent Henocque, Nicolas Prcovic},
title = {A Canonicity Test for Configuration},
booktitle = {proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP-2003)},
pages = {853-857},
address = {Kinsale, County Cork, Ireland },
month = {September},
year = {2003}},
}
- , "Handling Configuration Isomorphisms - Extended research report", pp. 1--37, July, 2008. [pdf] (abstract) (bibtex)
-
Natural language Processing
- , "Les grammaires de configuration : un cadre grammatical moderne", in: proceedings des troisièmes journées Francophones de Programmation par Contraintes, JFPC'07, pp. 111--120, Rocquencourt, France, Juin, 2007. [pdf] (abstract) (bibtex) link
abstract
Ce papier présente une nouvelle approche pour la description de grammaires du langage naturel et pour leur utilisation lors de l'analyse. Nous définissons un modèle objet contraint qui peut être étendu pour implémenter les formalismes grammaticaux et être ensuite exploité par un configurateur pour analyser syntaxiquement des phrases. Le cadre général se nomme Grammaires de Configuration et peut être utilisé pour la description de grammaires de dépendences comme pour celle de grammaires syntagmatiques. Nous proposons un exemple détaillé de cette application à un formalisme génératif à base de contraintes nommé les grammaires de propriétés.bibtex
@inproceedings {2007EstratatHenocque-JFPC,
author = {Mathieu Estratat, Laurent Henocque},
title = {Les grammaires de configuration : un cadre grammatical moderne},
booktitle = {proceedings des troisi\`{e}mes journ\'{e}es Francophones de Programmation par Contraintes, JFPC'07},
pages = {111--120},
address = {Rocquencourt, France},
month = {Juin},
year = {2007}},
} - , "Traduction automatique de grammaires à base
de traits en un problème de configuration
syntaxique", in: Proceedings of the deuxièmes journées Francophones de Programmation par Contraintes, JFPC'06, pp. 139--148, Nîmes, France, Juin, 2006. [pdf] (abstract) (bibtex)
abstract
Nous présentons un outil effectif de traduction au- tomatique d’une grammaire de propriété en un problème de configuration sous contraintes. Un template Latex (utilisant les AVMs1 standards) est utilisé pour spéci- fier la grammaire et le générateur prend en entrée les fichiers Latex utilisés pour la documenter. Ainsi, notre contribution propose à la fois une validation syntaxique des grammaires de propriété (l’outil détecte les inconsis- tances dans la grammaire au niveau de la formulation) et une manière de vérifier la correction et la consistance de la grammaire (en détectant les erreurs et/ou les éti- quetages manquant des phrases de test). L’approche pourrait se voir étendue à d’autres théories linguistiques basées sur les contraintes.bibtex
@inproceedings {EstratatHenocque06jfpc,
author = {Mathieu Estratat, Laurent Henocque},
title = {Traduction automatique de grammaires \`{a} base de traits en un probl\`{e}me de configuration syntaxique},
booktitle = {Proceedings of the deuxi\`{e}mes journ\'{e}es Francophones de Programmation par Contraintes, JFPC'06},
pages = {139--148},
address = {N\^{i}mes, France},
month = {Juin},
year = {2006}},
} - , "Vers les grammaires de configuration", in: Thèse de Doctorat de l'Université Paul Cézanne-Aix-Marseille III, pp. 1--152, Marseille, France, Novembre, 2006. [pdf] (abstract) (bibtex) link
abstract
The goal of this thesis is to use finite models search as a single natural language parsing framework at both syntactical and semantical points of view. For the syntax, the configuration grammars we propose offer a formal framework for the representation and studying of grammars. They allow the implementation of a syntactical parser, just by defining the grammar. The semantics treatment is based on descriptive texts (which describe objects). These syntactico-semantic treatments are described by constrained object models, formalized with the Z language. This method, new to the best of our knowledge in natural language analysis, presents the advantage of being independant from resolution technics.We are using a finite model search method, called configuration, for searching a solution out of an interpretation of the constrained object model.bibtex
@phdthesis {Estratat06PHD,
author = {Mathieu Estratat},
title = {Vers les grammaires de configuration},
booktitle = {Th\`{e}se de Doctorat de l'Universit\'{e} Paul C\'{e}zanne-Aix-Marseille III},
type = {Th\`{e}se de doctorat},
school = {Universit\'{e} Paul C\'{e}zanne-Aix-Marseille III},
pages = {1--152},
address = {Marseille, France},
month = {Novembre},
year = {2006}},
} - , "An interfacing module using configuration for declarative design of NURBS surfaces", in: Proceedings of the Ninth International Conference on Computer Graphics and Artificial Intelligence (3IA'2006), pp. 85 -- 96, Limoges, France, Mai, 2006. [pdf] (abstract) (bibtex)
abstract
Declarative modeling of surfaces is a powerful tool which aim is to assist designers dur- ing the creation step. These studies are focused on the mechanical area. The user has to give to the declarative system a description of the needed surface. After a solving process, the system returns one or more resulting NURBS surfaces if all the user requests can be satisfied. The designer can modify his description and restart the declarative process until he obtains the expected surface. A description is given to the system through interfacing modules which extract the relevant data and structures them into an XML tree. This paper is focused on a spe- cific interfacing module which takes a restricted french-written text as input. This interfacing module uses a recent constraint programming tool: configuration.bibtex
@inproceedings {EstratatLaGreca063IA,
author = {Mathieu Estratat, Rapha\:{e}l La Greca},
title = {An interfacing module using configuration for declarative design of NURBS surfaces},
booktitle = {Proceedings of the Ninth International Conference on Computer Graphics and Artificial Intelligence (3IA'2006)},
pages = {85 -- 96},
address = {Limoges, France},
month = {Mai},
year = {2006}},
} - , "Comprendre des Descriptions Simples à l'aide d'un Configurateur", in: Proceedings of the Premières Journées Francophones de Programmation par Contraintes, JFPC'2005, pp. 325--334, Lens, France, Juin, 2005. [pdf] (abstract) (bibtex)
abstract
The ultimate goal of natural language parsing is to build machine processable representations of text input. We present here a novel approach to this problem, that treats the combination of grammar parsing and building semantics as a single configuration task.Parsing using configurators is made possible by describing the gram- mar as a constrained object model. We extend the scope to semantics by introducing two new constrained object models : one for the semantical domain, and another that creates a bridge between syntax and semantics. We highlight some advantages of this approach, and present experimental results, in a restricted case of descriptive texts that can be further extended to capture richer semantics. The underlying constrained object system is for- mally presented using the Z relational language.bibtex
@inproceedings {EstratatHenocque05jfpc,
author = {Mathieu Estratat, Laurent Henocque},
title = {Comprendre des Descriptions Simples \`{a} l'aide d'un Configurateur},
booktitle = {Proceedings of the Premi\`{e}res Journ\'{e}es Francophones de Programmation par Contraintes, JFPC'2005},
pages = {325--334},
address = {Lens, France},
month = {Juin},
year = {2005}},
} - , "An Intuitive Tool for Constraint Based Grammars", in: Revised Selected and Invited Papers, Constraint Solving and Language Processing, First International Workshop, CSLP 2004, edited by Henning Christiansen, Peter Rossen Skadhauge, Jorgen Villadsen, publisher: Springer, series: Lecture Notes in Computer Science, volume 3438, pp. 121--139, Copenhagen, Denmark, September, 2005. [pdf] (abstract) (bibtex)
abstract
Recent linguistic theories are feature-based and heavily rely upon the concept of constraint. Several authors have pointed out the sim- ilarity existing between the representation of the features in feature-based theories and the notions of ob jects or frames. Ob ject-oriented configu- ration allows us to deal with these modern grammars. We propose here a systematic translation of the concepts and constraints introduced by two linguistic formalisms: the recent property grammars and the HPSG theory, to configuration problems representing specific target languages. We assess the usefulness of these translations by studying first a natural language subset with lexical ambiguities, using property grammars. De- tailed explanations on the solver’s behavior are given in this case. The article then presents a configuration model for a fragment of the HPSG grammar for English, together with details on implementing HPSG prin- ciples as configuration constraints.bibtex
@inproceedings {EstratatHenocque05cslprevised,
author = {Mathieu Estratat, Laurent Henocque},
title = {An Intuitive Tool for Constraint Based Grammars},
booktitle = {Revised Selected and Invited Papers, Constraint Solving and Language Processing, First International Workshop, CSLP 2004},
editor = {Henning Christiansen, Peter Rossen Skadhauge, Jorgen Villadsen},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {3438},
pages = {121--139},
address = {Copenhagen, Denmark},
month = {September},
year = {2005}},
isbn = {3--540-26165--6},
} - , "An Intuitive Tool for Constraint Based Grammars", in: Proceedings of the Workshop on Constraint Solving and Language Processing, CSLP 2004, edited by Henning Christiansen, Peter Rossen Skadhauge, Jorgen Villadsen, pp. 74--87, Roskilde University, Copenhagen, Denmark, September, 2004. (abstract) (bibtex)
abstract
Recent linguistic theories are feature-based and heavily rely upon the concept of constraint. Several authors have pointed out the sim- ilarity existing between the representation of the features in feature-based theories and the notions of ob jects or frames. Ob ject-oriented configu- ration allows us to deal with these modern grammars. We propose here a systematic translation of the concepts and constraints introduced by two linguistic formalisms: the recent property grammars and the HPSG theory, to configuration problems representing specific target languages. We assess the usefulness of these translations by studying first a natural language subset with lexical ambiguities, using property grammars. De- tailed explanations on the solver’s behavior are given in this case. The article then presents a configuration model for a fragment of the HPSG grammar for English, together with details on implementing HPSG prin- ciples as configuration constraints.bibtex
@inproceedings {EstratatHenocque04cslp,
author = {Mathieu Estratat, Laurent Henocque},
title = {An Intuitive Tool for Constraint Based Grammars},
booktitle = {Proceedings of the Workshop on Constraint Solving and Language Processing, CSLP 2004},
editor = {Henning Christiansen, Peter Rossen Skadhauge, Jorgen Villadsen},
pages = {74--87},
address = {Roskilde University, Copenhagen, Denmark},
month = {September},
year = {2004}},
} - , "Parsing languages with a configurator", in: Proceedings of the European Conference for Artificial Intelligence ECAI'2004, pp. 591--595, Valencia, Spain, August, 2004. [pdf] (abstract) (bibtex)
abstract
Recent evolution of linguistic theories heavily rely upon the concept of constraint. Also, several authors have pointed out the similitude existing between the categories of feature-based theories and the notions of objects or frames. We show that a generalization of constraint programs called configuration programs can be applied to natural language parsing. We propose here a systematic transla- tion of the concepts and constraints introduced by property grammars to configuration problems representing specific target languages. We assess the usefulness of this translation by studying first a recursive (context free) language with semantics, and a natural language sub- set with lexical ambiguities. Our experiments show the practical ef- ficiency of this approach, which does not require the use of ad hoc algorithms and can be freely used in analysis, generative, or hybrid mode.bibtex
@inproceedings {EstratatHenocque04ecai,
author = {Mathieu Estratat, Laurent Henocque},
title = {Parsing languages with a configurator},
booktitle = {Proceedings of the European Conference for Artificial Intelligence ECAI'2004},
pages = {591--595},
address = {Valencia, Spain},
month = {August},
year = {2004}},
} - , "Parser des languages avec un configurateur", in: Proceedings of the 10 ièmes journées Nationales sur la résolution pratique des problèmes NP-complets, JNPC'04, pp. 155--167, Angers, France, June, 2004. [pdf] (abstract) (bibtex)
abstract
Les évolutions récentes des théories linguistiques font largement appel au concept de contrainte. De plus, les caractéristiques générales des grammaires de traits ont conduit plu- sieurs auteurs à pointer la ressemblance existant entre ces notions et les objets ou frames. Nous montrons qu’une évolution des programmes de contraintes, appelée programmes de configu- ration, peut être appliquée à la reconnaissance de langages et proposons une traduction systé- matique des concepts et contraintes présentés dans les grammaires de propriétés en terme de problèmes de configuration. Nous validons cette traduction par son application tout d’abord à un langage (hors-contexte) récursif et à la sémantique associée, puis à un sous-ensemble du langage naturel contenant des ambiguïtés lexicales. Notre approche est une amélioration à la fois vis à vis des grammaires de propriété car la procédure de recherche est générique et vis à vis des implémentations par satisfactions de contraintes des grammaires de dépendance car la configuration est une extension des CSP. De plus, notre approche valide l’intégration de la sémantique associée aux langages. Nos expérimentations montrent l’efficacité pratique de cette approche qui ne requiert pas d’algorithmes ad hoc et permet une utilisation aussi bien analytique que générative ou encore hybride du programme.bibtex
@inproceedings {EstratatHenocque04jnpc,
author = {Mathieu Estratat, Laurent Henocque},
title = {Parser des languages avec un configurateur},
booktitle = {Proceedings of the 10 i\`{e}mes journ\'{e}es Nationales sur la r\'{e}solution pratique des probl\`{e}mes NP-complets, JNPC'04},
pages = {155--167},
address = {Angers, France},
month = {June},
year = {2004}},
} - , "Application des OOCP à l'analyse du langage naturel", in: Proceedings of Traitement Automatique du Langage Naturel TALN '04, pp. 163--172, Fès, Maroc, Avril, 2004. [pdf] (abstract) (bibtex)
abstract
Recent evolutions of linguistic theories heavily rely upon the concept of constraint. Also, sev- eral authors have pointed the similitude existing between the categories of feature based theories and the notions of objects or frames. A recent evolution of constraint programming to object oriented constraint programs (OOCP) can be applied to natural language parsing. We propose here a systematic translation of the concepts and constraints introduced by property grammars to an OOCP. We apply this translation to the archetypal context free language an bn , and show that this approach allows to both parse and generate, to account for the semantics in the same formalism, and also that it does not require the use of ad hoc algorithms.bibtex
@inproceedings {EstratatHenocque04taln,
author = {Mathieu Estratat, Laurent Henocque},
title = {Application des OOCP \`{a} l'analyse du langage naturel},
booktitle = {Proceedings of Traitement Automatique du Langage Naturel TALN '04},
pages = {163--172},
address = {F\`{e}s, Maroc},
month = {Avril},
year = {2004}},
} - , "Configuration à base de contraintes", in: Proceedings of the Journées Nationales du GDR I3, Septembre, 2002. [pdf] (abstract) (bibtex)
abstract
Configurer consiste à simuler la réalisation d’un produit complexe à partir de composants choisis dans un catalogue de types. L’industrie exploite depuis longtemps des configurateurs, que les progrès de la programmation par contraintes permettent d’envisager sous plusieurs angles. La dimension générative des problèmes de configuration peut être prise en compte au sein d’outils de programmation logique (CC, CLP, Modèles stables), par l’extension du strict cadre CSP (DCSP dynamiques, CSP génératifs, CSP structuraux), ou par des approches orientées objet autonomes ou reposant sur les logiques de description et termologiques. Cet article tente de présenter un aperçu synthétique des problèmes posés par la configuration, et des approches retenues.bibtex
@techreport {FargierHenocque02,
author = {H\'{e}l\`{e}ne Fargier, Laurent Henocque},
title = {Configuration \`{a} base de contraintes},
booktitle = {Proceedings of the Journ\'{e}es Nationales du GDR I3},
month = {Septembre},
year = {2002}},
}
- , "Les grammaires de configuration : un cadre grammatical moderne", in: proceedings des troisièmes journées Francophones de Programmation par Contraintes, JFPC'07, pp. 111--120, Rocquencourt, France, Juin, 2007. [pdf] (abstract) (bibtex) link
Other Resources
- , "Z Specification of Object Oriented Constraint Programs", RACSAM Revista Real Academia de Ciencias SerieA. Math., edited by Luis M. Laita, volume 98, pp. 127--152, Madrid, Spain, 2004. [pdf] (abstract) (bibtex)
abstract
Object oriented constraint programs (OOCPs) emerge as a leading evolution of constraint programming and artificial intelligence, first applied to a range of industrial applications called configu- ration problems. The rich variety of technical approaches to solving configuration problems (CLP(FD), CC(FD), DCSP, Terminological systems, constraint programs with set variables, . . . ) is a source of dif- ficulty. No universally accepted formal language exists for communicating about OOCPs, which makes the comparison of systems difficult. We present here a Z based specification of OOCPs which avoids the falltrap of hidden object semantics. The object system is part of the specification, and captures all of the most advanced notions from the object oriented modeling standard UML. The paper illustrates these issues and the conciseness and precision of Z by the specification of a working OOCP that solves an historical AI problem : parsing a context free grammar. Being written in Z, an OOCP specification also supports formal proofs. The whole builds the foundation of an adaptative and evolving framework for communicating about constrained object models and programs.bibtex
@article {2004Henocque-RACSAM,
author = {Laurent Henocque},
title = {Z Specification of Object Oriented Constraint Programs},
journal = {RACSAM Revista Real Academia de Ciencias SerieA. Math.},
editor = {Luis M. Laita},
volume = {98},
pages = {127--152},
address = {Madrid, Spain},
year = {2004}},
}
- , "Z Specification of Object Oriented Constraint Programs", RACSAM Revista Real Academia de Ciencias SerieA. Math., edited by Luis M. Laita, volume 98, pp. 127--152, Madrid, Spain, 2004. [pdf] (abstract) (bibtex)