The computational dichotomy of true-concurrency

Prelegent(ci)

Sibylle Froeschle

Termin

7 czerwca 2006 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---