@inbook{915b3d301ff6426c88f6552c61c8679c,
title = "Decidable and undecidable problems in schedulability analysis using timed automata",
abstract = "We study schedulability problems of timed systems with nonuniformly recurring computation tasks. Assume a set of real time tasks whose best and worst execution times, and deadlines are known. We use timed automata to describe the arrival patterns (and release times) of tasks. From the literature, it is known that the schedulability problem for a large class of such systems is decidable and can be checked efficiently. In this paper, we provide a summary on what is decidable and what is undecidable in schedulability analysis using timed automata. Our main technical contribution is that the schedulability problem will be undecidable if these three conditions hold: (1) the execution times of tasks are intervals, (2) a task can announce its completion time, and (3) a task can preempt another task. We show that if one of the above three conditions is dropped, the problem will be decidable. Thus our result can be used as an indication in identifying classes of timed systems that can be analysed efficiently.",
author = "Pavel Kr{\v c}{\'a}l and Wang Yi",
year = "2004",
doi = "10.1007/978-3-540-24730-2\_20",
language = "英语",
isbn = "354021299X",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "236--250",
editor = "Kurt Jensen and Andreas Podelski",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "德国",
}