D0L sequence equivalence is inPfor fixed alphabets
Keijo Ruohonen · RAIRO - Theoretical Informatics and Applications · 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.