RAIRO-Theor. Inf. Appl. 42, 361-374 (2008)
DOI: 10.1051/ita:2007037

D0L sequence equivalence is in P for fixed alphabets

Keijo Ruohonen

Institute of Mathematics, Tampere University of Technology, 33101 Tampere, Finland; keijo.ruohonen@tut.fi

(Received August 21, 2006. Accepted September 18, 2007. Published online 13 December 2007.)

Abstract
A new algorithm is presented for the D0L sequence equivalence problem which, when the alphabets are fixed, works in time polynomial in the rest of the input data. The algorithm uses a polynomial encoding of words and certain well-known properties of -rational sequences.

Mathematics Subject Classification. 68Q45

Key words: D0L system -- equivalence problem -- polynomial-time algorithm


© EDP Sciences 2007