Automata for words and trees find applications in diverse areas such as logic, verification, and database theory (see, e.g., [1]}, [2]}, [3]}). Applications to logic include proofs of decidability of the satisfiability problem for various logics, and this is the theme of this paper.
Many variations of automata for specific applications have been introduced, among them automata over infinite words or trees, with output, timed automata, or automata working on words and trees whose positions are annotated by data from an infinite domain. In this article we study a variant of the latter family of automata called register automata [4]}, [5]}.
