On the expressivity and complexity of quantitative branching-time temporal logics.

François Laroussinie 1 Philippe Schnoebelen 1 Mathieu Turuani 2
1 LSV - Laboratoire Spécification et Vérification [Cachan]
2 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We investigate extensions of CTL allowing to express quantitative requirements about an abstract notion of time in a simple discrete-time framework, and study the expressive power of several relevant logics. When only subscripted modalities are used, polynomial-time model checking is possible even for the largest logic we consider, while the introduction of freeze quantifiers leads to a complexity blow-up.
Keywords : CTL Branching-time temporal logic Discrete time Expressivity Model checking Complexity
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2003, Theoretical Computer Science, 1-3 (297), pp.297-315. 〈10.1016/S0304-3975(02)00644-8〉
Liste complète des métadonnées
https://hal.inria.fr/inria-00104145
Contributeur : Mathieu Turuani <>
Soumis le : jeudi 5 octobre 2006 - 18:01:58
Dernière modification le : vendredi 6 juillet 2018 - 15:06:09

Lien texte intégral

openaccess

Identifiants

Collections

INRIA | UNIV-FCOMTE | UNIV-BM | FEMTO-ST | UNIV-BM-THESE | ENS-CACHAN | LORIA | UNIV-LORRAINE

Citation

François Laroussinie, Philippe Schnoebelen, Mathieu Turuani. On the expressivity and complexity of quantitative branching-time temporal logics.. Theoretical Computer Science, Elsevier, 2003, Theoretical Computer Science, 1-3 (297), pp.297-315. 〈10.1016/S0304-3975(02)00644-8〉. 〈inria-00104145〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

201

Contact


archive-ouverte@inria.fr