A new, logical approach is propounded to resolve the decidability problem for the hierarchies of Straubing and Brzozowski based on preservation theorems in model theory, a theorem of Higman, and the Rabin tree theorem. We thus manage to obtain purely logical, short proofs of some known decidability facts, which definitely may be of methodological interest. The given approach also applies in some other similar situations, for instance, to the hierarchies of formulas modulo a theory of linear orderings with finitely many unary predicates. © 2002 Plenum Publishing Corporation.