---
_id: '12175'
abstract:
- lang: eng
  text: An automaton is history-deterministic (HD) if one can safely resolve its non-deterministic
    choices on the fly. In a recent paper, Henzinger, Lehtinen and Totzke studied
    this in the context of Timed Automata [9], where it was conjectured that the class
    of timed ω-languages recognised by HD-timed automata strictly extends that of
    deterministic ones. We provide a proof for this fact.
acknowledgement: This work was supported in part by the ERC-2020-AdG 101020093, the
  EPSRC project EP/V025848/1, and the EPSRC project EP/X017796/1.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Sougata
  full_name: Bose, Sougata
  last_name: Bose
- 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: Karoliina
  full_name: Lehtinen, Karoliina
  last_name: Lehtinen
- first_name: Sven
  full_name: Schewe, Sven
  last_name: Schewe
- first_name: Patrick
  full_name: Totzke, Patrick
  last_name: Totzke
citation:
  ama: 'Bose S, Henzinger TA, Lehtinen K, Schewe S, Totzke P. History-deterministic
    timed automata are not determinizable. In: <i>16th International Conference on
    Reachability Problems</i>. Vol 13608. Springer Nature; 2022:67-76. doi:<a href="https://doi.org/10.1007/978-3-031-19135-0_5">10.1007/978-3-031-19135-0_5</a>'
  apa: 'Bose, S., Henzinger, T. A., Lehtinen, K., Schewe, S., &#38; Totzke, P. (2022).
    History-deterministic timed automata are not determinizable. In <i>16th International
    Conference on Reachability Problems</i> (Vol. 13608, pp. 67–76). Kaiserslautern,
    Germany: Springer Nature. <a href="https://doi.org/10.1007/978-3-031-19135-0_5">https://doi.org/10.1007/978-3-031-19135-0_5</a>'
  chicago: Bose, Sougata, Thomas A Henzinger, Karoliina Lehtinen, Sven Schewe, and
    Patrick Totzke. “History-Deterministic Timed Automata Are Not Determinizable.”
    In <i>16th International Conference on Reachability Problems</i>, 13608:67–76.
    Springer Nature, 2022. <a href="https://doi.org/10.1007/978-3-031-19135-0_5">https://doi.org/10.1007/978-3-031-19135-0_5</a>.
  ieee: S. Bose, T. A. Henzinger, K. Lehtinen, S. Schewe, and P. Totzke, “History-deterministic
    timed automata are not determinizable,” in <i>16th International Conference on
    Reachability Problems</i>, Kaiserslautern, Germany, 2022, vol. 13608, pp. 67–76.
  ista: 'Bose S, Henzinger TA, Lehtinen K, Schewe S, Totzke P. 2022. History-deterministic
    timed automata are not determinizable. 16th International Conference on Reachability
    Problems. RC: Reachability Problems, LNCS, vol. 13608, 67–76.'
  mla: Bose, Sougata, et al. “History-Deterministic Timed Automata Are Not Determinizable.”
    <i>16th International Conference on Reachability Problems</i>, vol. 13608, Springer
    Nature, 2022, pp. 67–76, doi:<a href="https://doi.org/10.1007/978-3-031-19135-0_5">10.1007/978-3-031-19135-0_5</a>.
  short: S. Bose, T.A. Henzinger, K. Lehtinen, S. Schewe, P. Totzke, in:, 16th International
    Conference on Reachability Problems, Springer Nature, 2022, pp. 67–76.
conference:
  end_date: 2022-10-21
  location: Kaiserslautern, Germany
  name: 'RC: Reachability Problems'
  start_date: 2022-10-17
date_created: 2023-01-12T12:11:57Z
date_published: 2022-10-12T00:00:00Z
date_updated: 2023-09-05T15:12:08Z
day: '12'
department:
- _id: ToHe
doi: 10.1007/978-3-031-19135-0_5
ec_funded: 1
intvolume: '     13608'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://hal.science/hal-03849398/
month: '10'
oa: 1
oa_version: Preprint
page: 67-76
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
  call_identifier: H2020
  grant_number: '101020093'
  name: Vigilant Algorithmic Monitoring of Software
publication: 16th International Conference on Reachability Problems
publication_identifier:
  eisbn:
  - '9783031191350'
  eissn:
  - 1611-3349
  isbn:
  - '9783031191343'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: History-deterministic timed automata are not determinizable
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 13608
year: '2022'
...