Nie jesteś zalogowany |
Weak simulation problem for one counter nets
- Prelegent(ci)
- Piotr Hofman
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 31 października 2012 14:15
- Pokój
- p. 5870
- Seminarium
- Seminarium „Teoria automatów”
One counter net is actually a one counter automaton without a possibility of testing the value 0. For example it can recognize a language a^n b^m for m less or equal n. Weak simulation is a version of a simulation between objects which allow for epsilon (silent) moves. This provides a lot of problem if one try to deal with them.
I will present a sketch of an algorithm to solve the weak simulation between two one counter nets. Importance of this result comes from 2 directions. First of all, this result goes against well known intuition that bisimulation is easier than simulation (weak bisimulation is undecidable). Secondly this is the first result which solves a weak simulation for a quiet general class of infinite state systems (as far as I know).
I will present a sketch of an algorithm to solve the weak simulation between two one counter nets. Importance of this result comes from 2 directions. First of all, this result goes against well known intuition that bisimulation is easier than simulation (weak bisimulation is undecidable). Secondly this is the first result which solves a weak simulation for a quiet general class of infinite state systems (as far as I know).
