String execution time for finite languages : max is easy, min is hard

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

25 Citaten (Scopus)

Samenvatting

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. Keywords: Languages; Finite-state automata; (Max, +) semiring; Heap models; Computational complexity
Originele taal-2Engels
Pagina's (van-tot)2326-2329
Aantal pagina's4
TijdschriftAutomatica
Volume47
Nummer van het tijdschrift10
DOI's
StatusGepubliceerd - 2011

Vingerafdruk

Duik in de onderzoeksthema's van 'String execution time for finite languages : max is easy, min is hard'. Samen vormen ze een unieke vingerafdruk.

Citeer dit