A Decidable Fixpoint Logic for Time-Outs
*
Maria Sorea6 
| (6) |
Computer Science Laboratory, SRI International, 333 Ravenswood Avenue, 94025 Menlo Park, CA, USA |
Abstract
We show decidability of the satisfiability problem for an extension of the modal μ-calculus with event-recording clocks. Based
on techniques for deciding the untimed μ-calculus, we present a complete set of reduction rules for constructing tableaux
for formulas of this eventrecording logic. To keep track of the actual value of the clocks, the premises and conclusions of
our tableau rules are augmented with timing contexts, which are sets of timing constraints satisfied by the actual value of
the clocks. The decidability problem is shown to be EXPTIME complete. In addition, we address the problem of model synthesis,
that is, given a formula φ, we construct an event-recording automaton that satisfies φ.
This research was supported by the National Science Foundation under grants CCR-00-82560 and CCR-00-86096.
Also affiliated with University of Ulm, Germany.
References secured to subscribers.