D0L sequence equivalence is in P for fixed alphabets
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 2, pp. 361-374.

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.

DOI : 10.1051/ita:2007037
Classification : 68Q45
Mots-clés : D0L system, equivalence problem, polynomial-time algorithm 
@article{ITA_2008__42_2_361_0,
     author = {Ruohonen, Keijo},
     title = {D0L sequence equivalence is in $P$ for fixed alphabets},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {361--374},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {2},
     year = {2008},
     doi = {10.1051/ita:2007037},
     mrnumber = {2401267},
     zbl = {1144.68037},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita:2007037/}
}
TY  - JOUR
AU  - Ruohonen, Keijo
TI  - D0L sequence equivalence is in $P$ for fixed alphabets
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
SP  - 361
EP  - 374
VL  - 42
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita:2007037/
DO  - 10.1051/ita:2007037
LA  - en
ID  - ITA_2008__42_2_361_0
ER  - 
%0 Journal Article
%A Ruohonen, Keijo
%T D0L sequence equivalence is in $P$ for fixed alphabets
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2008
%P 361-374
%V 42
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita:2007037/
%R 10.1051/ita:2007037
%G en
%F ITA_2008__42_2_361_0
Ruohonen, Keijo. D0L sequence equivalence is in $P$ for fixed alphabets. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 2, pp. 361-374. doi : 10.1051/ita:2007037. http://archive.numdam.org/articles/10.1051/ita:2007037/

[1] M.H. Albert and J. Lawrence, A proof of Ehrenfeucht's conjecture. Theoret. Comput. Sci. 41 (1985) 121-123. | MR | Zbl

[2] J. Berstel and M. Mignotte, Deux problèmes décidables des suites récurrentes linéaires. Bull. Soc. Math. France 104 (1976) 175-184. | Numdam | MR | Zbl

[3] J. Berstel and C. Reutenauer, Rational Series and Their Languages. Springer-Verlag (1988). | MR | Zbl

[4] 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. | MR | Zbl

[5] K. Čulik Ii and I. Friš, The decidability of the equivalence problem for D0L-systems. Inform. Control 35 (1977) 20-39. | MR | Zbl

[6] 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. | Zbl

[7] A. Ehrenfeucht and G. Rozenberg, Elementary homomorphisms and a solution of the D0L sequence equivalence problem. Theoret. Comput. Sci. 7 (1978) 169-183. | MR | Zbl

[8] A. Ehrenfeucht and G. Rozenberg, On a bound for the D0L sequence equivalence problem. Theoret. Comput. Sci. 12 (1980) 339-342. | MR | Zbl

[9] V. Halava, T. Harju, M. Hirvensalo and J. Karhumäki, Skolem's Problem - On the Border Between Decidability and Undecidability. TUCS Technical Report No 683 (2005) (submitted).

[10] G. Hansel, Une démonstration simple du théorème de Skolem-Mahler-Lech. Theoret. Comput. Sci. 244 (1986) 91-98. | MR | Zbl

[11] J. Honkala, A short solution for the HDT0L sequence equivalence problem. Theoret. Comput. Sci. 244 (2000) 267-270. | MR | Zbl

[12] J. Honkala, A polynomial bound for certain cases of the D0L sequence equivalence problem. Theoret. Comput. Syst. 34 (2001) 263-272. | MR | Zbl

[13] 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. | MR | Zbl

[14] J. Honkala, An n 2 -bound for the ultimate equivalence problem of certain D0L systems over an n-letter alphabet. J. Comput. Syst. Sci. 71 (2005) 506-519. | MR | Zbl

[15] J. Honkala, A new bound for the D0L sequence equivalence problem. Acta Inform. 43 (2007) 419-429. | MR | Zbl

[16] J. Karhumäki, On the equivalence problem for binary D0L systems. Inform. Control 50 (1981) 276-284. | MR | Zbl

[17] 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. | MR | Zbl

[18] W. Magnus, On a theorem of Marshall Hall. Ann. Math. 40 (1954) 764-768. | Zbl

[19] G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems. Academic Press (1980). | MR | Zbl

[20] Handbook of Formal Languages. Vols. 1-3, edited by G. Rozenberg and A. Salomaa. Springer-Verlag (1997). | MR | Zbl

[21] K. Ruohonen, Test sets for iterated morphisms. Mathematics Report No 49. Tampere University of Technology (1986).

[22] 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. | Zbl

[23] K. Ruohonen, Solving equivalence of recurrent sequences in groups by polynomial manipulation. Fund. Inform. 38 (1999) 135-148. | MR | Zbl

[24] K. Ruohonen, Explicit test sets for iterated morphisms in free monoids and metabelian groups. Theoret. Comput. Sci. 330 (2005) 171 -191. | MR | Zbl

[25] A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series. Springer-Verlag (1978). | MR | Zbl

[26] W.M. Schmidt, The zero multiplicity of linear recurrence sequences. Acta Math. 182 (1999) 243-282. | MR | Zbl

Cité par Sources :