You are not logged in | Log in

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.