|
| What is CADP? |
|---|
|
Home Page
Tools Overview Current Status Recent Changes |
| Installation |
|
How to obtain CADP?
Usage Statistics |
| Documentation |
|
FAQ
Tutorials Publications Manual Pages Demo Examples Wikipedia |
| CADP Community |
|
Newsletters
Education & Training Case Studies Research Tools Forum |
| CADP Resources |
|
VLSAT Benchmarks
VLTS Benchmarks Other Resources |
| About CADP |
| Contributors |
| Organisation: |
University of Regina (CANADA)
|
|---|---|
| Method: |
LOTOS
|
| Tools used: |
CADP (Construction and Analysis of Distributed Processes)
|
| Domain: |
Constraint Programming.
|
| Period: |
2005
|
| Size: |
17 data types (500 lines of LOTOS)
|
| Description: |
Solving a CSP (constraint satisfaction problem) consists in computing
for a set of variables (defined on finite domains) an assignment that
respects a set of constraints. This case study describes the use of
LOTOS and CADP for CSP solving.
The basic idea is to represent the constraints in the data type part of LOTOS, so that the process part of LOTOS corresponds to the process of solving the CSP. In this way, the same LOTOS specification can be used to address different aspects of a CSP. First, the CSP is consistent if the LOTOS specification contains no deadlock. Second, simulation (respectively state space generation) corresponds to the generation of one solution (respectively all possible solutions). To reduce the execution time of the state space generation, the C code generated by CAESAR.ADT for the data type part of the LOTOS specification is combined with an external library, providing implementations of dedicated constraint propagation algorithms, such as arc consistency. Using this combination, the execution time is significantly reduced: in the 29-queens example, state space generation time is reduced by a factor of almost three. |
| Conclusions: |
The combination of the C code generated for LOTOS data types with
dedicated alogrithms for constraint propagation allows to
significantly reduce the execution time of the state space
computation.
The authors also note the quality of the code generated by CAESAR.ADT:
|
| Publications: |
[Mouhoub-Sadaoui-05]
M. Mouhoub and S. Sadaoui.
"Improving Lotos Simulation Using Constraint Propagation". In
Proceedings of the 17th IEEE International Conference on Tools with
Artificial Intelligence ICTAI'05 (Hong-Kong), December 2005.
Available on-line from the CADP Web site in PDF 
or
PostScript 
|
| Contact: | Dr. Samira Sadaoui-Mouhoub Assistant Professor Department of Computer Science University of Regina 3737 Wascana Parkway Regina, SK S4S 0A2 Canada Office: CW308.14 Tel: +1 306-337-2340 Fax: +1 306-585-4745 E-mail: sadaouis@cs.uregina.ca |
| Further remarks: | This case study, amongst others, is described on the CADP Web site: http://cadp.inria.fr/case-studies |
Back to the CADP case studies page