Nie jesteś zalogowany |
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
- 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.
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.
