Forest expressions

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

Uniwersytet Warszawski

Termin

25 kwietnia 2007 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---