Generalized discrete timed automata: decidable approximations for safety verification
✍ Scribed by Zhe Dang; Oscar H. Ibarra; Richard A. Kemmerer
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 175 KB
- Volume
- 296
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
We consider generalized discrete timed automata with general linear relations over clocks and parameterized constants as clock constraints and with parameterized durations. We look at three approximation techniques (i.e., the r-reset-bounded approximation, the B-bounded approximation, and the B; r -crossing-bounded approximation), and derive automata-theoretic characterizations of the binary reachability under these approximations. The characterizations allow us to show that the safety analysis problem is decidable for generalized discrete timed automata with unit durations and for deterministic generalized discrete timed automata with parameterized durations. An example speciÿcation written in ASTRAL is used to run a number of experiments using one of the approximation techniques.