You are not logged in |
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
- 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.
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.
