History-Deterministic Timed Automata Are Not Determinizable

Bose, Sougata, Henzinger, Thomas A, Lehtinen, Karoliina, Schewe, Sven ORCID: 0000-0002-9093-9518 and Totzke, Patrick ORCID: 0000-0001-5274-8190 (2022) History-Deterministic Timed Automata Are Not Determinizable. .

Text
main_submitted.pdf - Author Accepted Manuscript
Download (402kB) | Preview

Official URL: http://dx.doi.org/10.1007/978-3-031-19135-0_5

Abstract

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.

Item Type:	Conference or Workshop Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	23 Nov 2022 11:37
Last Modified:	22 Nov 2023 22:42
DOI:	10.1007/978-3-031-19135-0_5
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3166338