<_h,<_v)$ on finite tree

Speaker(s)

Thomas Place

Affiliation

Uniwersytet Warszawski

Date

Nov. 3, 2010, 2:15 p.m.

Room

room 5870

Title in Polish

Expressive power of $FO_2

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.

---