Universality Analysis for One-Clock Timed Automata

Journal article

This paper is concerned with the universality problem for timed automata: given a timed automaton A, does A accept all timed words? Alur and Dill have shown that the universality problem is undecidable if A has two clocks, but they left open the status of the problem when A has a single clock. In this paper we close this gap for timed automata over infinite words by showing that the one-clock universality problem is undecidable. For timed automata over finite words we show that the one-clock ...

Expand abstract

Authors: Abdulla, P; Deneux, J; Ouaknine, J; Quaas, K; Worrell, J

• Publication status: Published
• Journal: FUNDAMENTA INFORMATICAE
• Volume: 89
• Issue: 4
• Pages: 419-450
• Publication date: 2008-01-01
• ISSN: 0169-2968
• Language: English