This workpackage is concerned with the algorithmic basis of distributed timed systems: Basic algorithms for analysis and synthesis of timed systems, data structures and heuristics. The choice for timed automata as a basic model motivated by the fact that -- while being quite expressive -- the reachability, model checking and synthesis problems are known to be decidable (most often PSPACE-complete). The
challenge however is to adapt and to improve the algorithms so as to deal with big systems. The traditional approach currently implemented in the major tools suffers from the state explosion problem arising from analysis or synthesis of big composed systems. The tasks in this workpackage represent several working directions which the consortium will explore in parallel to be able to cope with realistic big systems in spite of the generally high complexity. To experimentally evaluate the practical
usefulness of techniques that are developed, substantial effort will be made in constructing prototype tools.