Generating Optimal Linear Temporal Logic Monitors by Coinduction

Koushik Sen and Grigore Rosu and Gul Agha
ASIAN'03 Springer-Verlag, Volume 2896, pp 260-275, December 2003

Abstract. A coinduction-based technique to generate an optimal monitor from a Linear Temporal Logic (LTL) formula is presented in this paper. Such a monitor receives a sequence of states (one at a time) from a running process, checks them against a requirements specification expressed as an LTL formula, and determines whether the formula has been violated or validated. It can also say whether the LTL formula is not monitorable any longer, i.e., that the formula can in the future neither be violated nor be validated. A Web interface for the presented algorithm adapted to extended regular expressions is available.