A Graph-Theoretic Approach for Timing Analysis and its Implementation
- 1 August 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-36 (8) , 961-975
- https://doi.org/10.1109/tc.1987.5009519
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
This publication has 5 references indexed in Scilit:
- Logic machine architecture: Inference mechanismsPublished by Springer Nature ,2005
- Safety analysis of timing properties in real-time systemsIEEE Transactions on Software Engineering, 1986
- Variable elimination and chaining in a resolution-based prover for inequalitiesPublished by Springer Nature ,1980
- Specifying Software Requirements for Complex Systems: New Techniques and Their ApplicationIEEE Transactions on Software Engineering, 1980
- A Practical Decision Procedure for Arithmetic with Function SymbolsJournal of the ACM, 1979