User: Guest  Login
Subtitle:
Preliminary Results
Title:

The Diameter of Binary Multithreaded Programs

Document type:
Report / Forschungsbericht
Author(s):
Alexander Malkis, Yutaka Nagashima, Steffen Borgwardt und Claudia Eckert
Abstract:
We consider the class of finite-state multithreaded programs equipped with a shared-memory interleaving semantics and study the possibility of useful asymptotic bounds on the (finite) diameter of the transition graph of a program from this class. This diameter gives an upper bound on the length of a shortest certificate for the existence of a bug in such a program and as such is connected to the complexity of bug-finding. We here study the dependency of the diameter on the number of threads fo...     »
Keywords:
concurrency, multithreading, multithreaded programs, transition graph, diameter, formal methods
Contracting organization:
Technische Universität München
Year:
2013
Monat:
Aug
Language:
en
Format:
Text
 BibTeX