Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
696690 | Automatica | 2011 | 4 Pages |
Abstract
In performance evaluation or supervisory control, we often encounter problems of determining the maximum or minimum string execution time for a finite language when estimating the worst-case or best-case performance. It has been shown in the literature that the time complexity for computing the maximum string execution time for a finite language is polynomial with respect to the size of an automaton recognizer of that language and the dimension of the corresponding resource matrices. In this paper we provide a more efficient algorithm to compute such maximum string execution time. Then we show that it is NP-complete to determine the minimum string execution time.
Related Topics
Physical Sciences and Engineering
Engineering
Control and Systems Engineering
Authors
Rong Su, Gerhard Woeginger,