D0L sequence equivalence is in P for fixed alphabets
Institute of Mathematics, Tampere University of Technology,
33101 Tampere, Finland; email@example.com
Accepted: 18 September 2007
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