T(A) = T(B)?
Géraud Sénizergues
(LABRI, Bordeaux)
Abstract
The equivalence problem for deterministic pushdown transducers with
inputs in a free monoid
and outputs in a linear group
, 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
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
into a free group
(or, a fortiori, a free monoid
), 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