Campus Event Calendar
Event Entry
New for: D1, D2, D3, D4, D5
What and Who
Analysis of Recursively Parallel Programs
Michael Emmi
LIAFA, Paris
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 30 August 2012
10:00
330 Minutes
G26
206
Kaiserslautern
Abstract
We propose a general formal model of isolated hierarchical parallel
computations, and identify several fragments to match the concurrency
constructs present in real-world programming languages such as Cilk
and X10. By associating fundamental formal models (vector addition
systems with recursive transitions) to each fragment, we provide a
common platform for exposing the relative difficulties of algorithmic
reasoning. For each case we measure the complexity of deciding
state-reachability for finite-data recursive programs, and propose
algorithms for the decidable cases. The complexities which include
PTIME, NP, EXPSPACE, and 2EXPTIME contrast with undecidable
state-reachability for recursive multi-threaded programs.
computations, and identify several fragments to match the concurrency
constructs present in real-world programming languages such as Cilk
and X10. By associating fundamental formal models (vector addition
systems with recursive transitions) to each fragment, we provide a
common platform for exposing the relative difficulties of algorithmic
reasoning. For each case we measure the complexity of deciding
state-reachability for finite-data recursive programs, and propose
algorithms for the decidable cases. The complexities which include
PTIME, NP, EXPSPACE, and 2EXPTIME contrast with undecidable
state-reachability for recursive multi-threaded programs.
Contact
--email hidden
Video Broadcast
Yes
Saarbrücken
E1 5
029
passcode not visible
logged in users only
Susanne Rock, 08/30/2012 09:16 -- Created document.