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.
Keywords: 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},
year = {2008},
publisher = {EDP Sciences},
volume = {42},
number = {2},
doi = {10.1051/ita:2007037},
mrnumber = {2401267},
zbl = {1144.68037},
language = {en},
url = {https://www.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 - https://www.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 https://www.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
[1] and , A proof of Ehrenfeucht's conjecture. Theoret. Comput. Sci. 41 (1985) 121-123. | Zbl | MR
[2] and , Deux problèmes décidables des suites récurrentes linéaires. Bull. Soc. Math. France 104 (1976) 175-184. | Zbl | MR | Numdam
[3] and , Rational Series and Their Languages. Springer-Verlag (1988). | Zbl | MR
[4] and , The presence of a zero in an integer linear recurrent sequence is NP-hard to decide. Linear Algebra Appl. 351-352 (2002) 91-98. | Zbl | MR
[5] and , The decidability of the equivalence problem for D0L-systems. Inform. Control 35 (1977) 20-39. | Zbl | MR
[6] and , 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] and , Elementary homomorphisms and a solution of the D0L sequence equivalence problem. Theoret. Comput. Sci. 7 (1978) 169-183. | Zbl | MR
[8] and , On a bound for the D0L sequence equivalence problem. Theoret. Comput. Sci. 12 (1980) 339-342. | Zbl | MR
[9] , , and , Skolem's Problem - On the Border Between Decidability and Undecidability. TUCS Technical Report No 683 (2005) (submitted).
[10] , Une démonstration simple du théorème de Skolem-Mahler-Lech. Theoret. Comput. Sci. 244 (1986) 91-98. | Zbl | MR
[11] , A short solution for the HDT0L sequence equivalence problem. Theoret. Comput. Sci. 244 (2000) 267-270. | Zbl | MR
[12] , A polynomial bound for certain cases of the D0L sequence equivalence problem. Theoret. Comput. Syst. 34 (2001) 263-272. | Zbl | MR
[13] , 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. | Zbl | MR
[14] , An -bound for the ultimate equivalence problem of certain D0L systems over an -letter alphabet. J. Comput. Syst. Sci. 71 (2005) 506-519. | Zbl | MR
[15] , A new bound for the D0L sequence equivalence problem. Acta Inform. 43 (2007) 419-429. | Zbl | MR
[16] , On the equivalence problem for binary D0L systems. Inform. Control 50 (1981) 276-284. | Zbl | MR
[17] , Diophantine equations: -adic methods, in Studies in Number Theory, edited by W.J. LeVeque. MAA Studies in Mathematics. Vol. 6 MAA (1969) 25-75. | Zbl | MR
[18] , On a theorem of Marshall Hall. Ann. Math. 40 (1954) 764-768. | Zbl
[19] and , The Mathematical Theory of L Systems. Academic Press (1980). | Zbl | MR
[20] Handbook of Formal Languages. Vols. 1-3, edited by G. Rozenberg and A. Salomaa. Springer-Verlag (1997). | Zbl | MR
[21] , Test sets for iterated morphisms. Mathematics Report No 49. Tampere University of Technology (1986).
[22] , 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] , Solving equivalence of recurrent sequences in groups by polynomial manipulation. Fund. Inform. 38 (1999) 135-148. | Zbl | MR
[24] , Explicit test sets for iterated morphisms in free monoids and metabelian groups. Theoret. Comput. Sci. 330 (2005) 171 -191. | Zbl | MR
[25] and , Automata-Theoretic Aspects of Formal Power Series. Springer-Verlag (1978). | Zbl | MR
[26] , The zero multiplicity of linear recurrence sequences. Acta Math. 182 (1999) 243-282. | Zbl | MR
Cité par Sources :
