Language Inclusion Checking of Timed Automata Based on Property Patterns

Abstract

The language inclusion checking of timed automata is described as the following: given two timed automata M and N, where M is a system model and N is a specification model (which represents the properties that the system needs to satisfy), check whether the language of M is included in the language of N. The language inclusion checking of timed automata can detect whether a system model satisfies a given property under the time constraints. There exist excellent studies on verifying real-time systems using timed automata. However, there is no thorough method of timed automata language inclusion checking for real-life systems. Therefore, this paper proposes a language inclusion checking method of timed automata based on the property patterns. On the one hand, we summarize commonly used property patterns described by timed automata, which can guide people to model the properties with time constraints. On the other hand, the system model M often contains a large number of events, but in general, the property N only needs to pay attention to the sequences and time limits of a few events. Therefore, the timed automata language inclusion checking algorithm is improved so that only the concerned events are required. Our method is applied to a water disposal system and it is also evaluated using benchmark systems. The determinization problem of timed automata is undecidable, which may lead to an infinite state space. However, our method is still practical because the properties established according to property patterns are often deterministic.

Keywords

• timed automata
• language inclusion
• property pattern
• verification