Decidability of the theory of the totally unbounded /spl omega/-layered structure

In this paper, we address the decision problem for a system of monadic second-order logic interpreted over an /spl omega/-layered temporal structure devoid of both a finest layer and a coarsest one (we call such a structure totally unbounded). We propose an automaton-theoretic method that solves the problem in two steps: first, we reduce the considered problem to the problem of determining, for any given Rabin tree automaton, whether it accepts a fixed vertex-colored tree; then, we exploit a suitable notion of tree equivalence to reduce the latter problem to the decidable case of regular trees.