---
_id: '4621'
abstract:
- lang: eng
  text: The  most  natural,  compositional,  way  of  modeling  real-time  systems  uses  a  dense
    domain  for  time.  The  satisfiability  of  timing  constraints  that  are  capable  of  expressing  punctuality
    in  this  model,  however,  is  known  to  be  undecidable.  We  introduce  a  temporal  language  that  can
    constrain  the  time  difference  between  events  only  with  finite,  yet  arbitrary,  precision  and  show  the
    resulting  logic  to  be  EXPSPACE-complete.  This  result  allows  us  to  develop  an  algorithm  for  the
    verification  of  timing  properties  of  real-time  systems  with  a  dense  semantics.
acknowledgement: 'We  wish  to  thank  an  anonymous  referee  for  pointing  out
  the  PSPACE-fragment  of  Section  4.5.  T. A. Henzinger was supported in part by
  the Office of Naval Research Young Investigator award NOOO14-95-l-0520, by the National
  Science Foundation CAREER award CCR 9501708, by the National Science Foundation
  grants CCR 92-00794 and CCR 9504469, by the Air Force Office of Scientific Research
  contract F49620-93-l-0056, and by the Advanced Research Projects Agency grant NAG2-892. '
article_processing_charge: No
author:
- first_name: Rajeev
  full_name: Alur, Rajeev
  last_name: Alur
- first_name: Tomás
  full_name: Feder, Tomás
  last_name: Feder
- 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: 'Alur R, Feder T, Henzinger TA. The benefits of relaxing punctuality. In: <i>Proceedings
    of the 10th Annual ACM Symposium on Principles of Distributed Computing</i>. ACM;
    1991:139-152. doi:<a href="https://doi.org/10.1145/227595.227602">10.1145/227595.227602</a>'
  apa: 'Alur, R., Feder, T., &#38; Henzinger, T. A. (1991). The benefits of relaxing
    punctuality. In <i>Proceedings of the 10th Annual ACM Symposium on Principles
    of Distributed Computing</i> (pp. 139–152). Montreal, Canada: ACM. <a href="https://doi.org/10.1145/227595.227602">https://doi.org/10.1145/227595.227602</a>'
  chicago: Alur, Rajeev, Tomás Feder, and Thomas A Henzinger. “The Benefits of Relaxing
    Punctuality.” In <i>Proceedings of the 10th Annual ACM Symposium on Principles
    of Distributed Computing</i>, 139–52. ACM, 1991. <a href="https://doi.org/10.1145/227595.227602">https://doi.org/10.1145/227595.227602</a>.
  ieee: R. Alur, T. Feder, and T. A. Henzinger, “The benefits of relaxing punctuality,”
    in <i>Proceedings of the 10th Annual ACM Symposium on Principles of Distributed
    Computing</i>, Montreal, Canada, 1991, pp. 139–152.
  ista: 'Alur R, Feder T, Henzinger TA. 1991. The benefits of relaxing punctuality.
    Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing.
    PODC: Principles of Distributed Computing, 139–152.'
  mla: Alur, Rajeev, et al. “The Benefits of Relaxing Punctuality.” <i>Proceedings
    of the 10th Annual ACM Symposium on Principles of Distributed Computing</i>, ACM,
    1991, pp. 139–52, doi:<a href="https://doi.org/10.1145/227595.227602">10.1145/227595.227602</a>.
  short: R. Alur, T. Feder, T.A. Henzinger, in:, Proceedings of the 10th Annual ACM
    Symposium on Principles of Distributed Computing, ACM, 1991, pp. 139–152.
conference:
  end_date: 1991-08-21
  location: Montreal, Canada
  name: 'PODC: Principles of Distributed Computing'
  start_date: 1991-08-19
date_created: 2018-12-11T12:09:48Z
date_published: 1991-01-01T00:00:00Z
date_updated: 2022-02-24T13:27:20Z
day: '01'
doi: 10.1145/227595.227602
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/doi/10.1145/227595.227602
month: '01'
oa_version: None
page: 139 - 152
publication: Proceedings of the 10th Annual ACM Symposium on Principles of Distributed
  Computing
publication_identifier:
  isbn:
  - 978-0-89791-439-0
publication_status: published
publisher: ACM
publist_id: '86'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The benefits of relaxing punctuality
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1991'
...