Language Inclusion Checking of Timed Automata with Non-Zenoness
- 16 January 2017
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. 43 (11) , 995-1008
Abstract
Given a timed automaton P modeling an implementation and a timed automaton S as a specification, the problem of language inclusion checking is to decide whether the language of P is a subset of that of S. It is known to be undecidable. The problem gets more complicated if non-Zenoness is taken into consideration. A run is Zeno if it permits infinitely many actions within finite time. Otherwise it is non-Zeno. Zeno runs might present in both P and S. It is necessary to check whether a run is Zeno or not so as to avoid presenting Zeno runs as counterexamples of language inclusion checking. In this work, we propose a zone-based semi-algorithm for language inclusion checking with non-Zenoness. It is further improved with simulation reduction based on LU-simulation. Though our approach is not guaranteed to terminate, we show that it does in many cases through empirical study. Our approach has been incorporated into the PAT model checker, and applied to multiple systems to show its usefulness.Keywords
Funding Information
- National Natural Science Foundation of China (61572426, 61373033, U1509214, 61602412)
- Singapore University of Technology and Design (T2MOE1303)
This publication has 34 references indexed in Scilit:
- Efficient emptiness check for timed Büchi automataFormal Methods in System Design, 2011
- Conformance testing for real-time systemsFormal Methods in System Design, 2009
- How to stop time stoppingFormal Aspects of Computing, 2006
- Patterns for Timed Property SpecificationsElectronic Notes in Theoretical Computer Science, 2006
- Lower and upper bounds in zone-based abstractions of timed automataInternational Journal on Software Tools for Technology Transfer, 2005
- Checking Timed Büchi Automata Emptiness EfficientlyFormal Methods in System Design, 2005
- Forward Analysis of Updatable Timed AutomataFormal Methods in System Design, 2004
- Event-clock automata: a determinizable class of timed automataTheoretical Computer Science, 1999
- Symbolic Model Checking for Real-Time SystemsInformation and Computation, 1994
- A theory of timed automataTheoretical Computer Science, 1994