D0L sequence equivalence is in P for fixed alphabets

Keijo Ruohonen

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2008)

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

Abstract

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

How to cite

top

Ruohonen, Keijo. "D0L sequence equivalence is in $P$ for fixed alphabets." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 42.2 (2008): 361-374. <http://eudml.org/doc/245083>.

@article{Ruohonen2008,
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 - Informatique Théorique et Applications},
keywords = {D0L system; equivalence problem; polynomial-time algorithm; polynomial encoding of words; -rational sequences},
language = {eng},
number = {2},
pages = {361-374},
publisher = {EDP-Sciences},
title = {D0L sequence equivalence is in $P$ for fixed alphabets},
url = {http://eudml.org/doc/245083},
volume = {42},
year = {2008},
}

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
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/245083
ER -

References

top
  1. [1] M.H. Albert and J. Lawrence, A proof of Ehrenfeucht’s conjecture. Theoret. Comput. Sci. 41 (1985) 121–123. Zbl0602.68066MR841029
  2. [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. Zbl0329.10009MR414475
  3. [3] J. Berstel and C. Reutenauer, Rational Series and Their Languages. Springer-Verlag (1988). Zbl0668.68005MR971022
  4. [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.93047MR1917474
  5. [5] K. Čulik II and I. Friš, The decidability of the equivalence problem for D0L-systems. Inform. Control 35 (1977) 20–39. Zbl0365.68074MR449030
  6. [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. Zbl0586.68066
  7. [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.68085MR509015
  8. [8] A. Ehrenfeucht and G. Rozenberg, On a bound for the D0L sequence equivalence problem. Theoret. Comput. Sci. 12 (1980) 339–342. Zbl0456.68085MR589315
  9. [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. [10] G. Hansel, Une démonstration simple du théorème de Skolem-Mahler-Lech. Theoret. Comput. Sci. 244 (1986) 91–98. Zbl0605.10007MR847905
  11. [11] J. Honkala, A short solution for the HDT0L sequence equivalence problem. Theoret. Comput. Sci. 244 (2000) 267–270. Zbl0945.68104MR1774399
  12. [12] J. Honkala, A polynomial bound for certain cases of the D0L sequence equivalence problem. Theoret. Comput. Syst. 34 (2001) 263–272. Zbl0988.68106MR1823124
  13. [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. Zbl1039.68067MR1941845
  14. [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. Zbl1082.68051MR2178078
  15. [15] J. Honkala, A new bound for the D0L sequence equivalence problem. Acta Inform. 43 (2007) 419–429. Zbl1106.68060MR2282860
  16. [16] J. Karhumäki, On the equivalence problem for binary D0L systems. Inform. Control 50 (1981) 276–284. Zbl0497.68048MR691593
  17. [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. Zbl0218.10035MR241359
  18. [18] W. Magnus, On a theorem of Marshall Hall. Ann. Math. 40 (1954) 764–768. Zbl0022.31403
  19. [19] G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems. Academic Press (1980). Zbl0508.68031MR561711
  20. [20] Handbook of Formal Languages. Vols. 1–3, edited by G. Rozenberg and A. Salomaa. Springer–Verlag (1997). Zbl0866.68057MR1469992
  21. [21] K. Ruohonen, Test sets for iterated morphisms. Mathematics Report No 49. Tampere University of Technology (1986). Zbl0612.68052
  22. [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. Zbl0612.68052
  23. [23] K. Ruohonen, Solving equivalence of recurrent sequences in groups by polynomial manipulation. Fund. Inform. 38 (1999) 135–148. Zbl0935.68134MR1718116
  24. [24] K. Ruohonen, Explicit test sets for iterated morphisms in free monoids and metabelian groups. Theoret. Comput. Sci. 330 (2005) 171 –191. Zbl1078.68094MR2112773
  25. [25] A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series. Springer–Verlag (1978). Zbl0377.68039MR483721
  26. [26] W.M. Schmidt, The zero multiplicity of linear recurrence sequences. Acta Math. 182 (1999) 243–282. Zbl0974.11013MR1710183

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.