2026-07-22T11:54:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12854 2024-03-06T10:50:51Z ddc:004 open_access

Determinisability of One-Clock Timed Automata Clemente, Lorenzo Lasota, Sławomir Piórkowski, Radosław Timed automata determinisation deterministic membership problem The deterministic membership problem for timed automata asks whether the timed language recognised by a nondeterministic timed automaton can be recognised by a deterministic timed automaton. We show that the problem is decidable when the input automaton is a one-clock nondeterministic timed automaton without epsilon transitions and the number of clocks of the deterministic timed automaton is fixed. We show that the problem in all the other cases is undecidable, i.e., when either 1) the input nondeterministic timed automaton has two clocks or more, or 2) it uses epsilon transitions, or 3) the number of clocks of the output deterministic automaton is not fixed. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lorenzo Clemente and Sławomir Lasota and Radosław Piórkowski 2020 Is Part Of LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2020.42 urn:nbn:de:0030-drops-128542 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.42 eng https://creativecommons.org/licenses/by/3.0/legalcode