Complexity of bisimulation equivalence

Prelegent(ci)

Slawomir Lasota

Afiliacja

Uniwersytet Warszawski

Termin

23 listopada 2005 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

An overview of known results and open problems in checking bisimulation equivalence on infinite graphs. In particular, graphs generated by context-free grammars and pushdown automata will be considered. Relationship to language equivalence will be pointed out, in particular for deterministic pushdown automata and for so called simple grammars.

---