IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca
IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.
AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.
EnglishTraces 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.
| Titolo: | Approximating the mean speedup in trace monoids |
| Autori: | BERTONI, ALBERTO (Primo) RADICIONI, ROBERTO (Ultimo) |
| Parole Chiave: | Trace monoids ; concurrent systems ; mean speedup ; uniform random generation |
| Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
| Data di pubblicazione: | giu-2008 |
| Rivista: | |
| Tipologia: | Article (author) |
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1142/S0129054108005796 |
| Appare nelle tipologie: | 01 - Articolo su periodico |
File in questo prodotto:
http://hdl.handle.net/2434/142777
Copyright © 2020