Abstract
This paper presents a graph-theoretic algorithm for safety analysis of a class of timing properties in real-time systems which are expressible in a subset of real time logic (RTL) formulas. Our procedure is in three parts: the first part constructs a graph representing the system specification and the negation of the safety assertion. The second part detects positive cycles in the graph using a node removal operation. The third part determines the consistency of the safety assertion with respect to the system specification based on the positive cycles detected. The implementation and an application of this procedure will also be described.
Keywords
AssertionComputer scienceGraphNegationConsistency (knowledge bases)Theoretical computer scienceAlgorithmProgramming language
Affiliated Institutions
Related Publications
Safety analysis of timing properties in real-time systems
The authors formalize the safety analysis of timing properties in real-time systems. The analysis is based on a formal logic, RTL (real-time logic), which is especially suitable...
ISO (International Organization for Standardization)
International Organization for Standardization (ISO) 21569:2005 describes the procedure to qualitatively detect genetically modified organisms and derived products by analyzing ...
A really temporal logic
A real-time temporal logic for the specification of reactive systems is introduced. The novel feature of the logic, TPTL, is the adoption of temporal operators as quantifiers ov...
Concurrent programming of intelligent robots
Real time intelligent robots usually consist of more than one processing unit (pu) to ensure parallel operation of several functions. Each pu in a robot executes repetitive moni...
Automatic verification of finite-state concurrent systems using temporal logic specifications
We give an efficient procedure for verifying that a finite-state concurrent system meets a specification expressed in a (propositional, branching-time) temporal logic. Our algor...
Publication Info
- Year
- 1987
- Type
- article
- Volume
- C-36
- Issue
- 8
- Pages
- 961-975
- Citations
- 153
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
153
OpenAlex
12
Influential
118
CrossRef
Cite This
Farnam Jahanian,
Aloysius K. Mok
(1987).
A Graph-Theoretic Approach for Timing Analysis and its Implementation.
IEEE Transactions on Computers
, C-36
(8)
, 961-975.
https://doi.org/10.1109/tc.1987.5009519
Identifiers
- DOI
- 10.1109/tc.1987.5009519