The Expressive Power of Clocks

Thomas A. Henzinger, Peter W. Kopke, Howard Wong-Toi

Abstract

We investigate the expressive power of timing restrictions on labeled transition systems. In particular, we show how constraints on clock variables together with a uniform liveness condition—the divergence of time—can express Büchi, Muller, Streett, Rabin, and weak and strong fairness conditions on a given labeled transition system. We then consider the effect, on both timed and time-abstract expressiveness, of varying the following parameters: time domain (discrete or dense), number of clocks, number of states, and size of constants used in timing restrictions.
BibTeX
@inproceedings{henzinger1995expressive,
  author = {Thomas A. Henzinger and Peter W. Kopke and Howard Wong-Toi},
  title = {{The Expressive Power of Clocks}},
  booktitle = {ICALP},
  year = {1995},
  doi = {10.1007/3-540-60084-1\_93},
}

Loading related content...

Figure