Fast equivalence checking for normed context-free processes. Joint work with Sławomir Lasota.

Prelegent(ci)

Wojciech Czerwiński

Afiliacja

Uniwersytet Warszawski

Termin

12 stycznia 2011 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

We consider graphs generated by context free grammars and ask the
question if given two states in such an infinite graph are equivalent.
I will talk about the new algorithm which answers this question using some
type of string compression. In fact it also solves the language equivalence question
for deterministic normed context free languages.
I will focus on ideas in this field rather than technical issues.

---