Properties of Binary Transitive Closure Logics over Trees
Stephan Kepser · 2006
Binary transitive closure logic (FOfor short) is the extension of first-order predicate logic by a transitive closure operator of binary relations. Determin- istic binary transitive closure logic (FO D� ) is the restriction of FOto deter- ministic transitive closures. It is known that these logics are more powerful than FO on arbitrary structures and on finite ordered trees. It is also known that they are at most as powerful as monadic second-order logic (MSO) on arbitrary structures and on finite trees. We will study the expressive power of FOand FO