Optimal-reachability and control for acyclic weighted timed automata

被引：0

作者：

La Torre, Salvatore ^{[1
,2
]}

Mukhopadhyay, Supratik ^{[1
]}

Murano, Aniello ^{[2
]}

机构：

[1] University of Pennsylvania, United States

[2] Università degli Studi di Salerno, Italy

来源：

IFIP Advances in Information and Communication Technology | 2002年 / 96卷

关键词：

Optimal control systems - Automata theory - Polynomial approximation;

D O I：

10.1007/978-0-387-35608-2_40

中图分类号：

学科分类号：

摘要：

Weighted timed automata extend timed automata with costs on both locations and transitions. In this framework we study the optimal reachability and the optimal control synthesis problems for the automata with acyclic control graphs. This class of automata is relevant for some practical problems such as some static scheduling problems or air-traffic control problems. We give a nondeterministic polynomial time algorithm to solve the decision version of the considered optimal reachability problem. This algorithm matches the known lower bound on the reachability for acyclic timed automata, and thus the problem is NPcomplete. We also solve in doubly exponential time the corresponding control synthesis problem.

引用

页码：485 / 497