Approximability and Non-approximability Results in Computing the Mean Speedup of Trace Monoids

DOI10.1007/978-3-540-73208-2_10zbMath1202.68263OpenAlexW1569479146MaRDI QIDQ5428221

Roberto Radicioni, Alberto Bertoni

Publication date: 28 November 2007

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-73208-2_10

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (1)

The number of convex permutominoes

Cites Work

• Unnamed Item
• Unnamed Item
• Computing the average parallelism in trace monoids.
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Concurrency measure in commutation monoids
• Combinatorial problems of commutation and rearrangements
• Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard
• On the Estimation of the Throughput for a Class of Stochastic Resources Sharing Systems
• Dynamics of synchronized parallel systems
• Performance evaluation of (max,+) automata

This page was built for publication: Approximability and Non-approximability Results in Computing the Mean Speedup of Trace Monoids