Paper Info
Title
Reachability in hierarchical machines
Abstract
In this paper we study the reachability analysis problem for timed systems specified in a hierarchical manner. First we provide a formal model, called hierarchical extended Mealy machine with timer, input and output events, as well with input, output and context variables. Then we present a synchronous semantics of the model. A main feature of this model is that the crossing of superstates' boundaries is forbidden, i.e., transitions between states in different superstates are not allowed. Finally we propose a reachability analysis method for finding (minimal) executions between configurations of a given deterministic hierarchical machine. Executions may require resetting of some constituent machines by entering some of their ancestor states. The algorithm exploits the hierarchical structure of the machine. The complexity of our algorithm is linear in R where R is the complexity of the reachability analysis of constituent machines.
Year
DOI
Venue
2014
10.1109/IRI.2014.7051927
Information Reuse and Integration
Keywords
Field
DocType
computational complexity,deterministic algorithms,finite automata,reachability analysis,algorithm complexity,ancestor states,constituent machines,context variables,deterministic hierarchical machine,formal model,hierarchical extended Mealy machine,hierarchical machines,reachability analysis problem,superstates boundaries,synchronous semantics,Hierarchical machine,discrete time,reachability analysis,synchronous semantics,test optimization
Test optimization,Computer science,Input/output,Theoretical computer science,Reachability,Artificial intelligence,Timer,Algorithm,Exploit,Mealy machine,Discrete time and continuous time,Machine learning,Semantics
Conference
Citations 
PageRank 
References 
1
0.36
26
Authors
4
Name
Order
Citations
PageRank
Omer Nguena-Timo1194.77
Alexandre Petrenko217615.90
Arnaud Dury320.70
Ramesh, S.414419.02