zbMATH — the first resource for mathematics

Folk theorems on the determinization and minimization of timed automata. (English) Zbl 1099.68648
Larsen, Kim G. (ed.) et al., Formal modeling and analysis of timed systems. First international workshop, FORMATS 2003, Marseille, France, September 6–7, 2003. Revised papers. Berlin: Springer (ISBN 3-540-21671-5/pbk). Lecture Notes in Computer Science 2791, 182-188 (2004).
Summary: Timed automata are known not to be complementable or determinizable. Natural questions are, then, could we check whether a given TA enjoys these properties? These problems are not algorithmically solvable, if we require not just a yes/no answer, but also a witness. Minimizing the “resources” of a TA (number of clocks or size of constants) are also unsolvable problems. Proofs are provided as simple reductions from the universality problem. These proofs are not applicable to the corresponding decision problems, the decidability of which remains open.
For the entire collection see [Zbl 1048.68006].

68Q45 Formal languages and automata
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Full Text: DOI