Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

A Decidable Fixpoint Logic for Time-Outs*

Maria SoreaContact Information

(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.

Contact Information Maria Sorea
Email: sorea@csl.sri.com
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.105 • Server: mpweb21
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)