We prove that equivalence of deterministic top-down tree-to-string transducers is decidable, thus solving a long-standing open problem in formal language theory. We also present efficient algorithms for subclasses: for linear transducers or total transducers with unary output alphabet (over a given top-down regular domain language), as well as for transducers with the single-use restriction. These results are obtained using techniques from multi-linear algebra. For our main result, we introduce polynomial transducers and prove that for these, validity of a polynomial invariant can be certified by means of an inductive invariant of polynomial ideals. This allows us to construct two semi-algorithms, one searching for a certificate of the invariant and one searching for a witness of its violation. Via a translation into polynomial transducers, we thus obtain that equivalence of general y dt transducers is decidable. In fact, our translation also shows that equivalence is decidable when the output is not in a free monoid but in a free group.

We show that equivalence of deterministic top-down tree-to-string transducers is decidable, thus solving a long standing open problem in formal language theory. We also present efficient algorithms for subclasses: polynomial time for total transducers with unary output alphabet (over a given top-down regular domain language), and co-randomized polynomial time for linear transducers, these results are obtained using techniques from multi-linear algebra. For our main result, we prove that equivalence can be certified by means of inductive invariants using polynomial ideals. This allows us to construct two semi-algorithms, one searching for a proof of equivalence, one for a witness of non-equivalence.

Invariant theory can be put in a very general context: If “∼” is an equivalence relation on a set X, then an invariant is a function on X which is constant on every equivalence class. So invariants serve to parametrize equivalence classes. The goals of invariant theory are to find all invariants that meet some further restrictions (such as continuity or polynomiality), and to study to which extent these invariants separate equivalence classes. For example, the determinant of a square matrix is an invariant w.r.t. the equivalence relation given by similarity. In the classical situation of invariant theory, the equivalence classes are given by the orbits of a group action. In fact, one considers the following setting: G is a linear algebraic group over an algebraically closed field K, and V is a finite-dimensional K-vector space with a linear G-action, given by a morphism G × V → V . In other words, we assume that the action can be described by polynomial functions. A natural extension is to substitute V by an affine K-variety X, which is then called a G-variety. The invariant ring