2 results
D0L sequence equivalence is in P for fixed alphabets
-
- Journal:
- RAIRO - Theoretical Informatics and Applications / Volume 42 / Issue 2 / April 2008
- Published online by Cambridge University Press:
- 13 December 2007, pp. 361-374
- Print publication:
- April 2008
-
- Article
- Export citation
-
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 $\mathbb{Z}$
-rational sequences.
On Sequences Defined by D0L Power Series
-
- Journal:
- RAIRO - Theoretical Informatics and Applications / Volume 33 / Issue 2 / March 1999
- Published online by Cambridge University Press:
- 15 August 2002, pp. 125-132
- Print publication:
- March 1999
-
- Article
- Export citation
-
We study D0L power series over commutative semirings. We show that a sequence(cn )n≥0 of nonzero elements of a field A is the coefficientsequence of a D0L power series if and only if there exist a positive integerk and integers βi for 1 ≤ i ≤ k such that $c_{n+k}=c_{n+k-1}^{\beta_1}c_{n+k-2}^{\beta_2}\ldots c_n^{\beta_k}$
for alln ≥ 0. As a consequence we solve the equivalence problem of D0L powerseries over computable fields.
