Henzinger, Thomas AIST Austria ; Kopke, Peter W ; Wong-Toi, Howard
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.
This research was supported in part by the National Science Foundation under grant CCR-9200794, by the United States Air Force Office of Scientific Research under contract F49620-93-1-0056, by the Defense Advanced Research Projects Agency under grant NAG2-892, and by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University, Contract Number DAAL03-91-C-0027. The full version of this paper is available from the Department of Computer Science, Cornell University, Ithaca, NY 14853, as Technical Report TR95-1496.
417 - 428
ICALP: Automata, Languages and Programming
Henzinger TA, Kopke P, Wong Toi H. The expressive power of clocks. In: Vol 944. Springer; 1995:417-428. doi:10.1007/3-540-60084-1_93
Henzinger, T. A., Kopke, P., & Wong Toi, H. (1995). The expressive power of clocks (Vol. 944, pp. 417–428). Presented at the ICALP: Automata, Languages and Programming, Springer. https://doi.org/10.1007/3-540-60084-1_93
Henzinger, Thomas A, Peter Kopke, and Howard Wong Toi. “The Expressive Power of Clocks,” 944:417–28. Springer, 1995. https://doi.org/10.1007/3-540-60084-1_93.
T. A. Henzinger, P. Kopke, and H. Wong Toi, “The expressive power of clocks,” presented at the ICALP: Automata, Languages and Programming, 1995, vol. 944, pp. 417–428.
Henzinger TA, Kopke P, Wong Toi H. 1995. The expressive power of clocks. ICALP: Automata, Languages and Programming, LNCS, vol. 944. 417–428.
Henzinger, Thomas A., et al. The Expressive Power of Clocks. Vol. 944, Springer, 1995, pp. 417–28, doi:10.1007/3-540-60084-1_93.