Real-time logics: Complexity and expressiveness Conference Paper


Author(s): Alur, Rajeev; Henzinger, Thomas A
Title: Real-time logics: Complexity and expressiveness
Affiliation
Abstract: A unifying framework for the study of real-time logics is developed. In analogy to the untimed case, the underlying classical theory of timed state sequences is identified, it is shown to be nonelementarily decidable, and its complexity and expressiveness are used as a point of reference. Two orthogonal extensions of PTL (timed propositional temporal logic and metric temporal logic) that inherit its appeal are defined: they capture elementary, yet expressively complete, fragments of the theory of timed state sequences, and thus are excellent candidates for practical real-time specification languages
Conference Title: LICS: Logic in Computer Science
Conference Dates: June 4 -7, 1990
Conference Location: Philadelphia, PA , USA
ISBN: 978-147998875-4
Publisher: IEEE  
Date Published: 1990-08-06
Start Page: 390
End Page: 401
URL:
DOI: 10.1109/LICS.1990.113764
Open access: no
IST Austria Authors
  1. Thomas A. Henzinger
    405 Henzinger
Related IST Austria Work