Realizability of Concurrent Recursive Programs

Benedikt Bollig 1, 2 Manuela-Lidia Grindei 2 Peter Habermehl 3
1 MEXICO - Modeling and Exploitation of Interaction and Concurrency
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : We define and study an automata model of concurrent recursive programs. An automaton consists of a finite number of pushdown systems running in parallel and communicating via shared actions. Actually, we combine multi-stack visibly pushdown automata and Zielonka's asynchronous automata towards a model with an undecidable emptiness problem. However, a reasonable restriction allows us to lift Zielonka's Theorem to this recursive setting and permits a logical characterization in terms of a suitable monadic second-order logic. Building on results from Mazurkiewicz trace theory and work by La Torre, Madhusudan, and Parlato, we thus develop a framework for the specification, synthesis, and verification of concurrent recursive processes.
Type de document :
Communication dans un congrès
de Alfaro, Luca. Proceedings of the 12th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS'09), 2009, York, UK, United Kingdom. Springer, 5504, pp.410-424, 2009, 〈10.1007/978-3-642-00596-1_29〉
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00772771
Contributeur : Benedikt Bollig <>
Soumis le : vendredi 11 janvier 2013 - 10:25:14
Dernière modification le : jeudi 11 janvier 2018 - 06:23:37
Document(s) archivé(s) le : vendredi 12 avril 2013 - 11:20:44

Fichier

BGH-fossacs09.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Benedikt Bollig, Manuela-Lidia Grindei, Peter Habermehl. Realizability of Concurrent Recursive Programs. de Alfaro, Luca. Proceedings of the 12th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS'09), 2009, York, UK, United Kingdom. Springer, 5504, pp.410-424, 2009, 〈10.1007/978-3-642-00596-1_29〉. 〈hal-00772771〉

Partager

Métriques

Consultations de la notice

163

Téléchargements de fichiers

101