Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/41484
Title: Incremental satisfiability counting for real-time systems
Authors: Andrei, Ş.
Chin, W.-N. 
Issue Date: 2004
Source: Andrei, Ş.,Chin, W.-N. (2004). Incremental satisfiability counting for real-time systems. Proceedings - IEEE Real-Time and Embedded Technology and Applications Symposium 10 : 482-489. ScholarBank@NUS Repository.
Abstract: 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 path RTL ([1, 5]). 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.
Source Title: Proceedings - IEEE Real-Time and Embedded Technology and Applications Symposium
URI: http://scholarbank.nus.edu.sg/handle/10635/41484
ISBN: 0769521487
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

45
checked on Dec 16, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.