Complexity of bisimulation equivalence

Speaker(s)

Slawomir Lasota

Affiliation

Uniwersytet Warszawski

Date

Nov. 23, 2005, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---