Reachability of Communicating Timed Processes

Lorenzo Clemente 1 Frédéric Herbreteau 1 Amélie Stainer 2 Grégoire Sutre 1
1 LaBRI - Laboratoire Bordelais de Recherche en Informatique
2 SUMO - SUpervision of large MOdular and distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
Abstract : We study the reachability problem for communicating timed processes, both in discrete and dense time. Our model comprises automata with local timing constraints communicating over unbounded FIFO channels. Each automaton can only access its set of local clocks; all clocks evolve at the same rate. Our main contribution is a complete characterization of decidable and undecidable communication topologies, for both discrete and dense time. We also obtain complexity results, by showing that communicating timed processes are at least as hard as Petri nets; in the discrete time, we also show equivalence with Petri nets. Our results follow from mutual topology-preserving reductions between timed automata and (untimed) counter automata.
Keywords : continuous time Reachability problem communicating timed processes discrete time continuous time.
Type de document :
Communication dans un congrès
Frank Pfenning. FoSSaCS - 16th International Conference on Foundations of Software Science and Computation Structures, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS - 2013, Mar 2013, Rome, Italy. Springer, 7794, pp.81-96, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-37075-5_6〉
Liste complète des métadonnées
https://hal.inria.fr/hal-00744085
Contributeur : Frédéric Herbreteau <>
Soumis le : lundi 22 octobre 2012 - 11:56:52
Dernière modification le : jeudi 15 novembre 2018 - 11:58:45

Lien texte intégral

arxiv

Identifiants

Collections

INRIA | LABRI | UNIV-BORDEAUX | UNIV-RENNES1 | IRISA | IRISA-D4 | INSTITUT-TELECOM | UR1-UFR-ISTIC | UNIV-RENNES

Citation

Lorenzo Clemente, Frédéric Herbreteau, Amélie Stainer, Grégoire Sutre. Reachability of Communicating Timed Processes. Frank Pfenning. FoSSaCS - 16th International Conference on Foundations of Software Science and Computation Structures, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS - 2013, Mar 2013, Rome, Italy. Springer, 7794, pp.81-96, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-37075-5_6〉. 〈hal-00744085〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

338

Contact


archive-ouverte@inria.fr