Forest expressions

Speaker(s)

Mikołaj Bojańczyk

Affiliation

Uniwersytet Warszawski

Date

April 25, 2007, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

I will talk about a type of regular expression for unranked trees. The main focus is on connections with logic: the expressions correspond to chain logic, the star-free expressions correspond to first-order logic, and finally, a concatenation hierarchy is shown to correspond to the quantifier alternation hierarchy.

---