---
_id: '4500'
abstract:
- lang: eng
  text: '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.'
acknowledgement: "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.\r\nThe
  full version of this paper is available from the Department of Computer Science,
  Cornell University, Ithaca, NY 14853, as Technical Report TR95-1496."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Peter
  full_name: Kopke, Peter
  last_name: Kopke
- first_name: Howard
  full_name: Wong Toi, Howard
  last_name: Wong Toi
citation:
  ama: 'Henzinger TA, Kopke P, Wong Toi H. The expressive power of clocks. In: <i>22nd
    International Colloquium on Automata, Languages and Programming </i>. Vol 944.
    Springer; 1995:417-428. doi:<a href="https://doi.org/10.1007/3-540-60084-1_93">10.1007/3-540-60084-1_93</a>'
  apa: 'Henzinger, T. A., Kopke, P., &#38; Wong Toi, H. (1995). The expressive power
    of clocks. In <i>22nd International Colloquium on Automata, Languages and Programming
    </i> (Vol. 944, pp. 417–428). Szeged, Hungary: Springer. <a href="https://doi.org/10.1007/3-540-60084-1_93">https://doi.org/10.1007/3-540-60084-1_93</a>'
  chicago: Henzinger, Thomas A, Peter Kopke, and Howard Wong Toi. “The Expressive
    Power of Clocks.” In <i>22nd International Colloquium on Automata, Languages and
    Programming </i>, 944:417–28. Springer, 1995. <a href="https://doi.org/10.1007/3-540-60084-1_93">https://doi.org/10.1007/3-540-60084-1_93</a>.
  ieee: T. A. Henzinger, P. Kopke, and H. Wong Toi, “The expressive power of clocks,”
    in <i>22nd International Colloquium on Automata, Languages and Programming </i>,
    Szeged, Hungary, 1995, vol. 944, pp. 417–428.
  ista: 'Henzinger TA, Kopke P, Wong Toi H. 1995. The expressive power of clocks.
    22nd International Colloquium on Automata, Languages and Programming . ICALP:
    Automata, Languages and Programming, LNCS, vol. 944, 417–428.'
  mla: Henzinger, Thomas A., et al. “The Expressive Power of Clocks.” <i>22nd International
    Colloquium on Automata, Languages and Programming </i>, vol. 944, Springer, 1995,
    pp. 417–28, doi:<a href="https://doi.org/10.1007/3-540-60084-1_93">10.1007/3-540-60084-1_93</a>.
  short: T.A. Henzinger, P. Kopke, H. Wong Toi, in:, 22nd International Colloquium
    on Automata, Languages and Programming , Springer, 1995, pp. 417–428.
conference:
  end_date: 1995-07-14
  location: Szeged, Hungary
  name: 'ICALP: Automata, Languages and Programming'
  start_date: 1995-07-10
date_created: 2018-12-11T12:09:10Z
date_published: 1995-01-01T00:00:00Z
date_updated: 2022-06-09T14:58:31Z
day: '01'
doi: 10.1007/3-540-60084-1_93
extern: '1'
intvolume: '       944'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-60084-1_93
month: '01'
oa_version: None
page: 417 - 428
publication: '22nd International Colloquium on Automata, Languages and Programming '
publication_identifier:
  isbn:
  - '9783540600848'
publication_status: published
publisher: Springer
publist_id: '229'
quality_controlled: '1'
status: public
title: The expressive power of clocks
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 944
year: '1995'
...
---
_id: '4518'
abstract:
- lang: eng
  text: The analysis, verification, and control of hybrid automata with finite bisimulations
    can be reduced to finite-state problems. We advocate a time-abstract, phase-based
    methodology for checking if a given hybrid automaton has a finite bisimulation.
    First, we factor the automaton into two components, a boolean automaton with a
    discrete dynamics on the finite state space B m and a euclidean automaton with
    a continuous dynamics on the infinite state space  n . Second, we investigate
    the phase portrait of the euclidean component. In this fashion, we obtain new
    decidability results for hybrid systems as well as new, uniform proofs of known
    decidability results.
acknowledgement: "This research was supported in part by the NSF grant CCR-9200794,
  by the AFOSR contract F49620-93-1-0056, and by the DARPA grant NAG2-892.\r\n"
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
citation:
  ama: 'Henzinger TA. Hybrid automata with finite bisimulations. In: <i>22nd International
    Colloquium on Automata, Languages and Programming </i>. Vol 944. Springer; 1995:324-335.
    doi:<a href="https://doi.org/10.1007/3-540-60084-1_85">10.1007/3-540-60084-1_85</a>'
  apa: 'Henzinger, T. A. (1995). Hybrid automata with finite bisimulations. In <i>22nd
    International Colloquium on Automata, Languages and Programming </i> (Vol. 944,
    pp. 324–335). Szeged, Hungary: Springer. <a href="https://doi.org/10.1007/3-540-60084-1_85">https://doi.org/10.1007/3-540-60084-1_85</a>'
  chicago: Henzinger, Thomas A. “Hybrid Automata with Finite Bisimulations.” In <i>22nd
    International Colloquium on Automata, Languages and Programming </i>, 944:324–35.
    Springer, 1995. <a href="https://doi.org/10.1007/3-540-60084-1_85">https://doi.org/10.1007/3-540-60084-1_85</a>.
  ieee: T. A. Henzinger, “Hybrid automata with finite bisimulations,” in <i>22nd International
    Colloquium on Automata, Languages and Programming </i>, Szeged, Hungary, 1995,
    vol. 944, pp. 324–335.
  ista: 'Henzinger TA. 1995. Hybrid automata with finite bisimulations. 22nd International
    Colloquium on Automata, Languages and Programming . ICALP: Automata, Languages
    and Programming, LNCS, vol. 944, 324–335.'
  mla: Henzinger, Thomas A. “Hybrid Automata with Finite Bisimulations.” <i>22nd International
    Colloquium on Automata, Languages and Programming </i>, vol. 944, Springer, 1995,
    pp. 324–35, doi:<a href="https://doi.org/10.1007/3-540-60084-1_85">10.1007/3-540-60084-1_85</a>.
  short: T.A. Henzinger, in:, 22nd International Colloquium on Automata, Languages
    and Programming , Springer, 1995, pp. 324–335.
conference:
  end_date: 1995-07-14
  location: Szeged, Hungary
  name: 'ICALP: Automata, Languages and Programming'
  start_date: 1995-07-10
date_created: 2018-12-11T12:09:16Z
date_published: 1995-01-01T00:00:00Z
date_updated: 2022-06-09T14:21:08Z
day: '01'
doi: 10.1007/3-540-60084-1_85
extern: '1'
intvolume: '       944'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-60084-1_85
month: '01'
oa_version: None
page: 324 - 335
publication: '22nd International Colloquium on Automata, Languages and Programming '
publication_identifier:
  isbn:
  - '9783540600848'
publication_status: published
publisher: Springer
publist_id: '212'
quality_controlled: '1'
status: public
title: Hybrid automata with finite bisimulations
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 944
year: '1995'
...