A Temporal Logic for Multi-threaded Programs

Abstract : Temporal logics for nested words are a specification formalism for procedural programs, since they express requirements about matching calls and returns. We extend this formalism to multiply nested words, which are natural models of the computations of concurrent programs. We study both the satisfiability and the model-checking problems, when the multiply nested words are runs of multi-stack pushdown systems (Mpds). In particular, through a tableau-based construction, we define a Büchi Mpds for the models of a given formula. As expected both problems are undecidable, thus we consider some meaningful restrictions on the Mpds, and show decidability for the considered problems.
Type de document :
Communication dans un congrès
Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.225-239, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_16〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01556217
Contributeur : Hal Ifip <>
Soumis le : mardi 4 juillet 2017 - 17:45:40
Dernière modification le : mardi 4 juillet 2017 - 17:47:02
Document(s) archivé(s) le : vendredi 15 décembre 2017 - 01:02:23

Fichier

978-3-642-33475-7_16_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Salvatore Torre, Margherita Napoli. A Temporal Logic for Multi-threaded Programs. Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.225-239, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_16〉. 〈hal-01556217〉

Partager

Métriques

Consultations de la notice

27

Téléchargements de fichiers

19