Traces can be viewed as parallel processes and the "mean speedup" of a trace monoid has been introduced as a measure of "intrinsic parallelism" of the monoid. We study the problem of computing the mean speedup under two conditions: uniform distribution on the words of given length and uniform distribution on the traces of given height. In the first case, we give an approximability result showing a probabilistic fully polynomial time approximation scheme, while, in the second case, we prove that the problem is NP-hard to approximate within n1-c for every ∊ > 0, unless NP = coR. A further consequence is the hardness of the problem of generating traces of a given height uniformly at random.
Approximating the mean speedup in trace monoids / A. Bertoni, R. Radicioni. - In: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - ISSN 0129-0541. - 19:3(2008 Jun), pp. 497-511.
Approximating the mean speedup in trace monoids
A. BertoniPrimo
;R. RadicioniUltimo
2008
Abstract
Traces can be viewed as parallel processes and the "mean speedup" of a trace monoid has been introduced as a measure of "intrinsic parallelism" of the monoid. We study the problem of computing the mean speedup under two conditions: uniform distribution on the words of given length and uniform distribution on the traces of given height. In the first case, we give an approximability result showing a probabilistic fully polynomial time approximation scheme, while, in the second case, we prove that the problem is NP-hard to approximate within n1-c for every ∊ > 0, unless NP = coR. A further consequence is the hardness of the problem of generating traces of a given height uniformly at random.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.