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
      0 references
      20 June 1999
      0 references
      branching temporal logics
      0 references
      model checking
      0 references
      complexity
      0 references
      program complexity
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references