Hierarchical and recursive state machines are suitable abstract models for many software systems. In this paper we extend a model recently introduced in literature, by allowing atomic propositions to label all the kinds of vertices and not only basic nodes. We call the obtained models context-dependent hierarchical/recursive state machines. We study on such models cycle detection, reachability and Ltl model-checking. Despite of a more succinct representation, we prove that Ltl model-checking can be done in time linear in the size of the model and exponential in the size of the formula, as for standard Ltl model-checking. Reachability and cycle detection become NP-complete, and if we place some restrictions on the representation of the target states, we can decide them in time linear in the size of the formula and the size of the model.

Hierarchical and Recursive State Machines with Context-Dependent Properties

PARLATO G.
2003-01-01

Abstract

Hierarchical and recursive state machines are suitable abstract models for many software systems. In this paper we extend a model recently introduced in literature, by allowing atomic propositions to label all the kinds of vertices and not only basic nodes. We call the obtained models context-dependent hierarchical/recursive state machines. We study on such models cycle detection, reachability and Ltl model-checking. Despite of a more succinct representation, we prove that Ltl model-checking can be done in time linear in the size of the model and exponential in the size of the formula, as for standard Ltl model-checking. Reachability and cycle detection become NP-complete, and if we place some restrictions on the representation of the target states, we can decide them in time linear in the size of the formula and the size of the model.
2003
9783540404934
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11695/88428
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact