Augmenting branching temporal logics with existential quantification over atomic propositions (Q4242583)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1286042
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Augmenting branching temporal logics with existential quantification over atomic propositions |
scientific article; zbMATH DE number 1286042 |
Statements
Augmenting branching temporal logics with existential quantification over atomic propositions (English)
0 references
20 June 1999
0 references
branching temporal logics
0 references
model checking
0 references
complexity
0 references
program complexity
0 references
0.8180211186408997
0 references
0.8081324100494385
0 references
0.8052714467048645
0 references
Temporal-logic model checking is used in verification of program correctness. The complexity of model-checking algorithms on finite propositional Kripke structures was established previously, in particular for the temporal logics CTL and CTL*. The author explores the relevant complexities when we enrich CTL and CTL* by existential quantification over atomic propositions. By this enrichment, the structure semantics and the (unfolded) computation tree semantics differ. This yields four cases to examine. Besides the complexity of the model checking problem (where the instance is a finite-state program and a formula), the author also studies, in each of the four cases, the so-called program complexity (when the formula is fixed). Therefore the paper contains eight complexity results, varying from P-completeness to 2EXPTIME-completeness.
0 references