# D0L sequence equivalence is in P for fixed alphabets

RAIRO - Theoretical Informatics and Applications (2007)

- Volume: 42, Issue: 2, page 361-374
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topRuohonen, Keijo. "D0L sequence equivalence is in P for fixed alphabets." RAIRO - Theoretical Informatics and Applications 42.2 (2007): 361-374. <http://eudml.org/doc/92876>.

@article{Ruohonen2007,

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 $\mathbb\{Z\}$-rational sequences.
},

author = {Ruohonen, Keijo},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {D0L system; equivalence problem; polynomial-time algorithm; polynomial encoding of words; -rational sequences},

language = {eng},

month = {12},

number = {2},

pages = {361-374},

publisher = {EDP Sciences},

title = {D0L sequence equivalence is in P for fixed alphabets},

url = {http://eudml.org/doc/92876},

volume = {42},

year = {2007},

}

TY - JOUR

AU - Ruohonen, Keijo

TI - D0L sequence equivalence is in P for fixed alphabets

JO - RAIRO - Theoretical Informatics and Applications

DA - 2007/12//

PB - EDP Sciences

VL - 42

IS - 2

SP - 361

EP - 374

AB -
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.

LA - eng

KW - D0L system; equivalence problem; polynomial-time algorithm; polynomial encoding of words; -rational sequences

UR - http://eudml.org/doc/92876

ER -

## References

top- M.H. Albert and J. Lawrence, A proof of Ehrenfeucht's conjecture. Theoret. Comput. Sci.41 (1985) 121–123. Zbl0602.68066
- J. Berstel and M. Mignotte, Deux problèmes décidables des suites récurrentes linéaires. Bull. Soc. Math. France104 (1976) 175–184. Zbl0329.10009
- J. Berstel and C. Reutenauer, Rational Series and Their Languages. Springer-Verlag (1988). Zbl0668.68005
- V.D. Blondel and N. Portier, The presence of a zero in an integer linear recurrent sequence is NP-hard to decide. Linear Algebra Appl.351–352 (2002) 91–98. Zbl1007.93047
- K. Čulik II and I. Friš, The decidability of the equivalence problem for D0L-systems. Inform. Control35 (1977) 20–39. Zbl0365.68074
- K. Čulik II and J. Karhumäki, A new proof for the D0L sequence equivalence problem and its implications, in The Book of L, edited by G. Rozenberg and A. Salomaa. Springer-Verlag (1986) 63–74. Zbl0586.68066
- A. Ehrenfeucht and G. Rozenberg, Elementary homomorphisms and a solution of the D0L sequence equivalence problem. Theoret. Comput. Sci.7 (1978) 169–183. Zbl0407.68085
- A. Ehrenfeucht and G. Rozenberg, On a bound for the D0L sequence equivalence problem. Theoret. Comput. Sci.12 (1980) 339–342. Zbl0456.68085
- V. Halava, T. Harju, M. Hirvensalo and J. Karhumäki, Skolem's Problem — On the Border Between Decidability and Undecidability. TUCS Technical Report No683 (2005) (submitted).
- G. Hansel, Une démonstration simple du théorème de Skolem-Mahler-Lech. Theoret. Comput. Sci.244 (1986) 91–98. Zbl0605.10007
- J. Honkala, A short solution for the HDT0L sequence equivalence problem. Theoret. Comput. Sci.244 (2000) 267–270. Zbl0945.68104
- J. Honkala, A polynomial bound for certain cases of the D0L sequence equivalence problem. Theoret. Comput. Syst.34 (2001) 263–272. Zbl0988.68106
- J. Honkala, The equivalence problem of polynomially bounded D0L systems — a bound depending only on the size of the alphabet. Theoret. Comput. Syst.36 (2003) 89–103. Zbl1039.68067
- J. Honkala, An n2-bound for the ultimate equivalence problem of certain D0L systems over an n-letter alphabet. J. Comput. Syst. Sci.71 (2005) 506–519. Zbl1082.68051
- J. Honkala, A new bound for the D0L sequence equivalence problem. Acta Inform.43 (2007) 419–429. Zbl1106.68060
- J. Karhumäki, On the equivalence problem for binary D0L systems. Inform. Control50 (1981) 276–284. Zbl0497.68048
- D.J. Lewis, Diophantine equations: p-adic methods, in Studies in Number Theory, edited by W.J. LeVeque. MAA Studies in Mathematics. Vol.6 MAA (1969) 25–75.
- W. Magnus, On a theorem of Marshall Hall. Ann. Math.40 (1954) 764–768. Zbl0022.31403
- G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems. Academic Press (1980). Zbl0508.68031
- Handbook of Formal Languages. Vols. 1–3, edited by G. Rozenberg and A. Salomaa. Springer–Verlag (1997).
- K. Ruohonen, Test sets for iterated morphisms. Mathematics Report No49. Tampere University of Technology (1986). Zbl0612.68052
- K. Ruohonen, Equivalence problems for regular sets of word morphisms, in The Book of L, edited by G. Rozenberg and A. Salomaa. Springer-Verlag (1986) 393–401.
- K. Ruohonen, Solving equivalence of recurrent sequences in groups by polynomial manipulation. Fund. Inform.38 (1999) 135–148. Zbl0935.68134
- K. Ruohonen, Explicit test sets for iterated morphisms in free monoids and metabelian groups. Theoret. Comput. Sci.330 (2005) 171 –191. Zbl1078.68094
- A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series. Springer–Verlag (1978). Zbl0377.68039
- W.M. Schmidt, The zero multiplicity of linear recurrence sequences. Acta Math.182 (1999) 243–282. Zbl0974.11013

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.