loading...
Incremental Satisfiability Counting for Real-Time Systems
Toronto, Canada May 25-May 28
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/RTTAS.2004.131729510th IEEE Real-Time and Embedded Tech ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Stefan Andrei, National University of Singapore
Wei-Ngan Chin, National University of Singapore
Testing constraints for real-time systems are usually verified through the satisfiability of propositional formulae. In this paper, we propose an alternative where the verification of timing constraints can be done by counting the number of truth assignments instead of boolean satisfiability. This number can also tell us how "far away" a given specification is from satisfying its safety assertion. Furthermore, specifications and safety assertions are often modified in an incremental fashion, where problematic bugs are fixed one at a time. To support this development, we propose an incremental algorithm for counting satisfiability. Our proposed incremental algorithm is optimal as no unnecessary nodes are created during each counting. This works for the class of expressions, known as pathRTL ([A graph-theoretic approach for timing analysis and its implementation, RTL and refutation by positive cycles]). To illustrate this application, we show how incremental satisfiability counting can be applied to a well-known rail-road crossing example, particularly when its specification is still being refined.
Citation:
Stefan Andrei, Wei-Ngan Chin, "Incremental Satisfiability Counting for Real-Time Systems," rtas, pp.482, 10th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.