On the equivalence of Z-automata
Marie-Pierre Béal,
Sylvain Lombardy, and
Jacques Sakarovitch
Abstract
We prove that two automata with multiplicity in Z are equivalent,
i.e. define the same rational series, if and only if there
is a sequence of Z-coverings, co-Z-coverings, and circulations
of -1, which transforms one automaton into the other.
Moreover, the construction of these transformations is effective.
This is obtained by combining two results:
the first one relates coverings to conjugacy of automata, and is
modeled after a theorem from symbolic dynamics;
the second one is an adaptation of Schützenberger's reduction algorithm
of representations in a field to representations in an Euclidean
domain (and thus in~Z).
Last modification:
2 February 2006