Reachability problem for stateless multi-pushdown automata

Prelegent(ci)

Piotr Hofman

Afiliacja

Uniwersytet Warszawski

Termin

12 października 2011 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Sławek Lasota and Wojtek Czerwiński

Seminarium

Seminarium „Teoria automatów”

---

It is well known that multi-pushdown automata are Turing complete.
However, one obtains an interesting class under assumption that the
automata have only one state. Surprisingly, the reachability problem
becames decidable and the complexity isn't as high as one might
expect. During the talk I will prove that the set of predecessors of a
regular set of configurations is always a regular set. In particular,
I will discuss a proper definition of regularity.

---