| Abstract |
|
In this paper, we address the decision problem for a system
of monadic second-order logic interpreted over an ω-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.
|
 Additional Information
|
Citation:
Angelo Montanari, Gabriele Puppis,
"Decidability of the Theory of the Totally Unbounded ⍵-Layered Structure,"
time,
pp. 156-160,
11th International Symposium on Temporal Representation and Reasoning (TIME'04),
2004
|
