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

Speaker(s)

Piotr Hofman

Affiliation

Uniwersytet Warszawski

Date

Oct. 12, 2011, 2:15 p.m.

Room

room 5870

Title in Polish

Reachability problem for stateless multi-pushdown automata

Seminar

Seminar Automata Theory

---

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.

---