Extending Two-Variable Logic on Trees

Bartosz Bednarczyk, Witold Charatonik, Emanuel Kieroński

The finite satisfiability problem for the two-variable fragment of first-order logic interpreted over trees was recently shown to be ExpSpace-complete. We consider two extensions o…