CIAA2003

START ConferenceManager

Timing Parameter Characterization of Real-Time Systems

Farn Wang and Hsu-Chun Yen

Presented at Eighth International Conference on Implementation and Application of Automata (CIAA 2003), July 16-18, 2003 Santa Barbara, CA, USA

Abstract

We investigate the problem of characterizing the solution spaces for timed automata augmented by unknown timing parameters (called timing parameter automata (TPA)). The main contribution of this paper is that we identify three non-trivial subclasses of TPAs, namely, upper-bound, lower-bound and bipartite TPAs, and analyze how hard it is to characterize the solution space. As it turns out, we are able to give complexity bounds for the sizes of the minimal (resp., maximal) elements which completely characterize the upward-closed (resp., downward-closed) solution spaces of upper-bound (resp., lower-bound) TPAs. For bipartite TPAs, it is shown that their solution spaces are not semilinear in general. We also extend our analysis to TPAs equipped with counters without zero-test capabilities.