T(A) = T(B)?

Géraud Sénizergues

(LABRI, Bordeaux)

Abstract
The equivalence problem for deterministic pushdown transducers with inputs in a free monoid tex2html_wrap_inline16 and outputs in a linear group tex2html_wrap_inline18 , is shown to be decidable.
We first reduce the problem to the equivalence problem for deterministic rational series on the alphabet associated with a dpdt tex2html_wrap_inline20 and with coefficients in the group H. We then exhibit a formal system which generates only equivalent pairs of such series. Conversely, every pair of equivalent series admits a regular proof. Using previous works on test-sets, we show that the set of ``regular'' proofs is recursively enumerable.
As a corollary, the equivalence problem for dpdt's from a free monoid tex2html_wrap_inline16 into a free group tex2html_wrap_inline26 (or, a fortiori, a free monoid tex2html_wrap_inline28 ), is decidable.

Keywords
deterministic pushdown transducers; rational series; finite dimensional vector spaces; matrix semi-groups; test-sets; complete formal systems.

Reference
report nr 1209-99, LaBRI, can be accessed at URL: http://www.labri.u-bordeaux.fr/~ges