Timed Bounded Verification of Inclusion Based on Timed Bounded Discretized Language
- 6 January 2021
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 32 (02) , 175-202
Abstract
The inclusion problem is one of the common problems in real-time systems. The general form of this problem is undecidable; however, the time-bounded verification of inclusion problem is decidable for timed automata. In this study, we propose a new discretization technique to verify the inclusion problem. The proposed technique is applied to a non-Zeno timed automaton with an upper bound that does not contain a non-reachable space for each transition. The new approach is based on the generation of timed bounded discretized language that represents an abstraction of timed words in the form of a set of a countable number of discrete timed words. A discrete timed word aggregates all timed words that share the same actions and their execution times that create the time continuous intervals. The lower and the upper bounds of an interval in a discrete timed word is defined by the minimum and maximum execution times associated to a given transition-run. In addition, we propose the verification schema of the inclusion between two timed bounded discretized languages generated by two non-Zeno timed automata.Keywords
This publication has 8 references indexed in Scilit:
- Language Inclusion Checking of Timed Automata with Non-ZenonessIEEE Transactions on Software Engineering, 2017
- Are Timed Automata Bad for a Specification Language? Language Inclusion Checking for Timed Automata2014
- Towards a Theory of Time-Bounded VerificationLecture Notes in Computer Science, 2010
- When Are Timed Automata Determinizable?2009
- Timed Automata with Integer Resets: Language Inclusion and Expressiveness2008
- Universality and Language Inclusion for Open and Closed Timed AutomataLecture Notes in Computer Science, 2003
- Event-clock automata: a determinizable class of timed automataTheoretical Computer Science, 1999
- A theory of timed automataTheoretical Computer Science, 1994