Strict LT2: Regular:: Local: Recognizable

We provide a characterization of the local sets (sets of trees generated by CFGs) in terms of definability in a restricted logical language, which we contrast with a similar characterization of the recognizable sets (sets of trees accepted by finite-state tree automata). In a strong sense, the distinction between these two captures abstractly the distinction between ordinary CFGs and those in which labels are finitely extended with additional features (as in GPSG). In terms of descriptive complexity, the contrast is quite profound--while the recognizable sets axe characterized by a monadic second-order language, the local sets axe characterized by a severely restricted modal language. In the domain of strings, there is an analogous contrast between the regular languages and the strict 2-locally testable languages, a weak subclass of the star-free sets