Name
Title | ||
|---|---|---|
A Timed Failure Equivalence Preserving Abstraction For Parametric Time-Interval Automata |
Abstract | ||
|---|---|---|
In the development of real-time communicating hardware/embedded-software systems, it is frequently the case that we want to refine/optimize the system's internal behavior while preserving the external timed 1/0 behavior. In such a design refinement, modification of the systems' internal branching structures, as well as re-scheduling of internal actions, may frequently occur. Our goal is, then, to ensure that such modification of internal branching structures and re-scheduling of internal actions preserve the systems' external timed behavior, which is typically formalized by the notion of (timed) failure equivalence since it is less sensitive to the difference of internal branching structures than (timed) weak bisimulation. In order to know the degree of freedom of such re-scheduling, parametric analysis is useful. One of the models suitable for such an analysis is a parametric time-interval autoniaton(PTIA), which is a subclass of the existing model, a parametric timed automaton. It has only a time interval with upper- and lower-bound parameters as a relative timing constraint between consecutive actions. In this paper, at first, we propose an abstraction algorithm of PTIA which preserves timed failure equivalence. Timed failure equivalence is strictly weaker than timed weak bisimulation in the sense that it does not distinguish the difference of the timing when the internal resolution of nondeterminism. has occurred, but it does distinguish the difference of the refusals of communicating actions observed by an external environment. Then, we also show that after applying our algorithm, the reduced PTIA has no internal actions, and thus the problem deriving a parameter condition in order that given two models are timed failure equivalent can be reduced to the existing parametric strong bisimulation equivalence checking. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1142/S0129054106004133 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
real-time communicating systems, parametric timed automata, equivalence checking, timed failure equivalence, abstraction | Formal equivalence checking,Discrete mathematics,Degrees of freedom (statistics),Abstraction,Automaton,Algorithm,Timed automaton,Equivalence (measure theory),Parametric statistics,Bisimulation,Mathematics | Journal |
Volume | Issue | ISSN |
17 | 4 | 0129-0541 |
Citations | PageRank | References |
0 | 0.34 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Akio Nakata | 1 | 106 | 10.07 |
| Tadaaki Tanimoto | 2 | 2 | 1.75 |
| Suguru Sasaki | 3 | 0 | 0.68 |
| Teruo Higashino | 4 | 1086 | 119.60 |