We study tree languages that can be defined in𝚫₁. These are tree languages definable by a first-orderformula whose quantifier prefix is forall exists, and simultaneouslyby a first-order formula whose quantifier prefix is . For thequantifier free part we consider two signatures, either the descendantrelation alone or together with the lexicographical order relation onnodes. We provide an effective characterization of tree and forestlanguages definable in 𝚫₁. This characterization is interms of algebraic equations. Over words, the class of word languagesdefinable in 𝚫₁ forms a robust class, which was givenan effective algebraic characterization by Pin and Weil.
展开▼
