<_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.