D0L sequence equivalence is in P for fixed alphabets
Ruohonen, Keijo
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 361-374 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2008-01-01
DOI : https://doi.org/10.1051/ita:2007037
Classification:  68Q45 
@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},
     volume = {42},
     year = {2008},
     pages = {361-374},
     doi = {10.1051/ita:2007037},
     mrnumber = {2401267},
     zbl = {1144.68037},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 361-374. doi : 10.1051/ita:2007037. http://gdmltest.u-ga.fr/item/ITA_2008__42_2_361_0/

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

[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 414475 | Zbl 0329.10009

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

[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 1917474 | Zbl 1007.93047

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

[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 0586.68066

[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 509015 | Zbl 0407.68085

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

[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 847905 | Zbl 0605.10007

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

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

[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 1941845 | Zbl 1039.68067

[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 2178078 | Zbl 1082.68051

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

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

[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 241359 | Zbl 0218.10035

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

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

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

[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 0612.68052

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

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

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

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