joint work with Patrick Totzke and Richard Mayr

Speaker(s)

Piotr Hofman

Affiliation

Uniwersytet Warszawski

Date

Oct. 31, 2012, 2:15 p.m.

Room

room 5870

Title in Polish

Weak simulation problem for one counter nets

Seminar

Seminar Automata Theory

---

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

---