S. Andrei, W.-N. Chin

Counting the number of truth assignments in a propositional formula has a number of applications, including the verification of timing constraints for real-time specification. This number can tell us how “far away” is a given specification from satisfying its safety assertion.

However, specifications and safety assertions are often modified in an incremental fashion, where problematic bugs are fixed one at a time. To mirror such changes, we propose an incremental algorithm for counting satisfiability. Our proposed incremental algorithm is optimal as no unnecessary nodes are created during each incremental counting. To illustrate this application, we show how incremental satisfiability counting can be applied to a well-known rail-road crossing example, when its specification is being modified.

A concise and revised version of the paper was accepted at the 10th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2004).

Full Document (PS)

Bibtex

@TechReport{cav,
    author = 	"S. Andrei and  W.-N. Chin",
    title = 	"Incremental {C}ounting {S}atisfiability for {R}eal-{T}ime {S}ystems",
    institution = "``Al.I.Cuza'' University of Ia{c s}i, Faculty of Computer Science",
    year = 	"2003",
    number = 	"TR 03-04",
    url = 	"https://publications.info.uaic.ro/technical-reports/archive/tr03-04-2003-incremental-counting-satisfiability-for-real-time-systems/"
}