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

Tytuł w języku angielskim

joint work with Patrick Totzke and Richard Mayr

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).

---