D0L sequence equivalence is in P for fixed alphabets. (English) Zbl 1144.68037
Summary: 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.
References:
| [1] | M.H. Albert and J. Lawrence, A proof of Ehrenfeucht’s conjecture. Theoret. Comput. Sci.41 (1985) 121-123. · Zbl 0602.68066 · doi:10.1016/0304-3975(85)90066-0 |
| [2] | 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 · Zbl 0329.10009 |
| [3] | J. Berstel and C. Reutenauer, Rational Series and Their Languages. Springer-Verlag (1988). · 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. Zbl1007.93047 · Zbl 1007.93047 · doi:10.1016/S0024-3795(01)00466-9 |
| [5] | K. Čulik II and I. Friš, The decidability of the equivalence problem for D0L-systems. Inform. Control35 (1977) 20-39. Zbl0365.68074 · Zbl 0365.68074 · doi:10.1016/S0019-9958(77)90512-5 |
| [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. Zbl0407.68085 · Zbl 0407.68085 · doi:10.1016/0304-3975(78)90047-6 |
| [8] | A. Ehrenfeucht and G. Rozenberg, On a bound for the D0L sequence equivalence problem. Theoret. Comput. Sci.12 (1980) 339-342. · Zbl 0456.68085 · doi:10.1016/0304-3975(80)90064-X |
| [9] | 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). |
| [10] | G. Hansel, Une démonstration simple du théorème de Skolem-Mahler-Lech. Theoret. Comput. Sci.244 (1986) 91-98. · Zbl 0605.10007 · doi:10.1016/0304-3975(86)90168-4 |
| [11] | J. Honkala, A short solution for the HDT0L sequence equivalence problem. Theoret. Comput. Sci.244 (2000) 267-270. · Zbl 0945.68104 · doi:10.1016/S0304-3975(00)00158-4 |
| [12] | J. Honkala, A polynomial bound for certain cases of the D0L sequence equivalence problem. Theoret. Comput. Syst.34 (2001) 263-272. · Zbl 0988.68106 · doi:10.1007/s00224-001-0001-2 |
| [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. · Zbl 1039.68067 · doi:10.1007/s00224-002-1075-1 |
| [14] | 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. · Zbl 1082.68051 · doi:10.1016/j.jcss.2005.05.003 |
| [15] | J. Honkala, A new bound for the D0L sequence equivalence problem. Acta Inform.43 (2007) 419-429. · Zbl 1106.68060 · doi:10.1007/s00236-006-0028-6 |
| [16] | J. Karhumäki, On the equivalence problem for binary D0L systems. Inform. Control50 (1981) 276-284. · Zbl 0497.68048 · doi:10.1016/S0019-9958(81)90367-3 |
| [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. · Zbl 0218.10035 |
| [18] | W. Magnus, On a theorem of Marshall Hall. Ann. Math.40 (1954) 764-768. · Zbl 0022.31403 · doi:10.2307/1968892 |
| [19] | G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems. Academic Press (1980). · Zbl 0508.68031 |
| [20] | Handbook of Formal Languages. Vols. 1-3, edited by G. Rozenberg and A. Salomaa. Springer-Verlag (1997). · Zbl 0866.68057 |
| [21] | K. Ruohonen, Test sets for iterated morphisms. Mathematics Report No49. Tampere University of Technology (1986). · Zbl 0612.68052 |
| [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. · 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. · Zbl 1078.68094 · doi:10.1016/j.tcs.2004.09.017 |
| [25] | A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series. Springer-Verlag (1978). · Zbl 0377.68039 |
| [26] | W.M. Schmidt, The zero multiplicity of linear recurrence sequences. Acta Math.182 (1999) 243-282. · Zbl 0974.11013 · doi:10.1007/BF02392575 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
