---
_id: '4594'
abstract:
- lang: eng
  text: "The authors introduce two-way timed automata-timed automata that can move
    back and forth while reading a timed word. Two-wayness in its unrestricted form
    leads, like nondeterminism, to the undecidability of language inclusion. However,
    if they restrict the number of times an input symbol may be revisited, then two-wayness
    is both harmless and desirable. The authors show that the resulting class of bounded
    two-way deterministic timed automata is closed under all boolean operations, has
    decidable (PSPACE-complete) emptiness and inclusion problems, and subsumes all
    decidable real-time logics we know. They obtain a strict hierarchy of real-time
    properties: deterministic timed automata can accept more languages as the bound
    on the number of times an input symbol may be revisited is increased. This hierarchy
    is also enforced by the number of alternations between past and future operators
    in temporal logic. The combination of the results leads to a decision procedure
    for a real-time logic with past operators\r\n"
article_processing_charge: No
author:
- first_name: Rajeev
  full_name: Alur, Rajeev
  last_name: Alur
- 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, Henzinger TA. Back to the future: Towards a theory of timed regular
    languages. In: <i>Proceedings of the 33rd Annual Symposium on Foundations of Computer
    Science</i>. IEEE; 1992:177-186. doi:<a href="https://doi.org/10.1109/SFCS.1992.267774">10.1109/SFCS.1992.267774</a>'
  apa: 'Alur, R., &#38; Henzinger, T. A. (1992). Back to the future: Towards a theory
    of timed regular languages. In <i>Proceedings of the 33rd Annual Symposium on
    Foundations of Computer Science</i> (pp. 177–186). Pittsburgh, PA, United States
    of America: IEEE. <a href="https://doi.org/10.1109/SFCS.1992.267774">https://doi.org/10.1109/SFCS.1992.267774</a>'
  chicago: 'Alur, Rajeev, and Thomas A Henzinger. “Back to the Future: Towards a Theory
    of Timed Regular Languages.” In <i>Proceedings of the 33rd Annual Symposium on
    Foundations of Computer Science</i>, 177–86. IEEE, 1992. <a href="https://doi.org/10.1109/SFCS.1992.267774">https://doi.org/10.1109/SFCS.1992.267774</a>.'
  ieee: 'R. Alur and T. A. Henzinger, “Back to the future: Towards a theory of timed
    regular languages,” in <i>Proceedings of the 33rd Annual Symposium on Foundations
    of Computer Science</i>, Pittsburgh, PA, United States of America, 1992, pp. 177–186.'
  ista: 'Alur R, Henzinger TA. 1992. Back to the future: Towards a theory of timed
    regular languages. Proceedings of the 33rd Annual Symposium on Foundations of
    Computer Science. FOCS: Foundations of Computer Science, 177–186.'
  mla: 'Alur, Rajeev, and Thomas A. Henzinger. “Back to the Future: Towards a Theory
    of Timed Regular Languages.” <i>Proceedings of the 33rd Annual Symposium on Foundations
    of Computer Science</i>, IEEE, 1992, pp. 177–86, doi:<a href="https://doi.org/10.1109/SFCS.1992.267774">10.1109/SFCS.1992.267774</a>.'
  short: R. Alur, T.A. Henzinger, in:, Proceedings of the 33rd Annual Symposium on
    Foundations of Computer Science, IEEE, 1992, pp. 177–186.
conference:
  end_date: 1992-10-27
  location: Pittsburgh, PA, United States of America
  name: 'FOCS: Foundations of Computer Science'
  start_date: 1992-10-24
date_created: 2018-12-11T12:09:39Z
date_published: 1992-01-01T00:00:00Z
date_updated: 2022-03-07T10:45:34Z
day: '01'
doi: 10.1109/SFCS.1992.267774
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://ieeexplore.ieee.org/document/267774
month: '01'
oa_version: None
page: 177 - 186
publication: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science
publication_status: published
publisher: IEEE
publist_id: '115'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Back to the future: Towards a theory of timed regular languages'
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1992'
...