Expressive power of $FO_2

Prelegent(ci)

Thomas Place

Afiliacja

Uniwersytet Warszawski

Termin

3 listopada 2010 14:15

Pokój

p. 5870

Tytuł w języku angielskim

<_h,<_v)$ on finite tree

Seminarium

Seminarium „Teoria automatów”

---

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.

---