Satisfiability of the Two-Variable Fragment of First-Order Logic over Trees

Witold Charatonik, Emanuel Kieroński, Filip Mazowiecki

We consider the satisfiability problem for the two-variable fragment of first-order logic over finite unranked trees. We work with signatures consisting of some unary predicates an…