Abstract

In the past decades, classical results from algebra, including Hilbert's Basis Theorem, had various applications in formal languages, including a proof of the Ehrenfeucht Conjecture, decidability of HDT0L sequence equivalence, and decidability of the equivalence problem for functional tree-to-string transducers. In this paper, we study the scope of the algebraic methods mentioned above, particularily as applied to the equivalence problem for register automata. We provide two results, one positive, one negative. The positive result is that equivalence is decidable for MSO transformations on unordered forests. The negative result comes from a try to extend this method to decide equivalence on macro tree transducers. We reduce macro tree transducers equivalence to an equivalence problem for some class of register automata naturally relevant to our method. We then prove this latter problem to be undecidable.