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

Speaker(s)

Wojciech Czerwiński

Affiliation

Uniwersytet Warszawski

Date

Jan. 12, 2011, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---