Published in

MDPI, Applied Sciences, 24(12), p. 12946, 2022

DOI: 10.3390/app122412946

Links

Tools

Export citation

Search in Google Scholar

Language Inclusion Checking of Timed Automata Based on Property Patterns

Journal article published in 2022 by Ting Wang ORCID, Yan Shen, Tieming Chen, Baiyang Ji, Tiantian Zhu, Mingqi Lv
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Green circle
Preprint: archiving allowed
Green circle
Postprint: archiving allowed
Green circle
Published version: archiving allowed
Data provided by SHERPA/RoMEO

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.