You are not logged in | Log in

The computational dichotomy of true-concurrency

Sibylle Froeschle
June 7, 2006, 2:15 p.m.
room 5870
Seminar Automata Theory

In concurrency theory there is a divide between the interleaving approach, in which concurrency is reduced to nondeterministic sequentialization, and the truly-concurrent approach, which represents concurrency in a more faithful way. In this talk I will give an inroduction to true-concurrency, and survey results and open problems in the area. In particular I will address the computational dichotomy of true-concurrency: for finite-state systems truly-concurrent paradigms are typically computationally harder than their interleaving counterparts while for restricted finite-state as well as infinite- state classes this effect is often reversed.