Tree Languages Defined in First-Order Logic with One Quantifier Alternation

Mikolaj Bojanczyk, Luc Segoufin

We study tree languages that can be defined in Δ_2 . These are tree languages definable by a first-order formula whose quantifier prefix is forall exists, and simultaneously by a f…