You are not logged in | Log in

<_h,<_v)$ on finite tree

Speaker(s)
Thomas Place
Affiliation
Uniwersytet Warszawski
Date
Nov. 3, 2010, 2:15 p.m.
Room
room 5870
Seminar
Seminar Automata Theory

I will present results about the expressive power of
$FO_2(<_h,<_v)$ on finite trees. In particular I will present a
characterization of this logic on finite trees. $FO_2(<_h,<_v)$
is the two variable fragment of first order logic built from the
descendant and following sibling predicates. The characterization
uses (partially) forest algebras.