D0L sequence equivalence is in P for fixed alphabets

Keijo Ruohonen

RAIRO - Theoretical Informatics and Applications (2007)

  • 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 42.2 (2007): 361-374. <http://eudml.org/doc/92876>.

@article{Ruohonen2007,
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},
keywords = {D0L system; equivalence problem; polynomial-time algorithm; polynomial encoding of words; -rational sequences},
language = {eng},
month = {12},
number = {2},
pages = {361-374},
publisher = {EDP Sciences},
title = {D0L sequence equivalence is in P for fixed alphabets},
url = {http://eudml.org/doc/92876},
volume = {42},
year = {2007},
}

TY - JOUR
AU - Ruohonen, Keijo
TI - D0L sequence equivalence is in P for fixed alphabets
JO - RAIRO - Theoretical Informatics and Applications
DA - 2007/12//
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/92876
ER -

References

top
  1. M.H. Albert and J. Lawrence, A proof of Ehrenfeucht's conjecture. Theoret. Comput. Sci.41 (1985) 121–123.  
  2. J. Berstel and M. Mignotte, Deux problèmes décidables des suites récurrentes linéaires. Bull. Soc. Math. France104 (1976) 175–184.  
  3. J. Berstel and C. Reutenauer, Rational Series and Their Languages. Springer-Verlag (1988).  
  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.  
  5. K. Čulik II and I. Friš, The decidability of the equivalence problem for D0L-systems. Inform. Control35 (1977) 20–39.  
  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.  
  7. A. Ehrenfeucht and G. Rozenberg, Elementary homomorphisms and a solution of the D0L sequence equivalence problem. Theoret. Comput. Sci.7 (1978) 169–183.  
  8. A. Ehrenfeucht and G. Rozenberg, On a bound for the D0L sequence equivalence problem. Theoret. Comput. Sci.12 (1980) 339–342.  
  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.  
  11. J. Honkala, A short solution for the HDT0L sequence equivalence problem. Theoret. Comput. Sci.244 (2000) 267–270.  
  12. J. Honkala, A polynomial bound for certain cases of the D0L sequence equivalence problem. Theoret. Comput. Syst.34 (2001) 263–272.  
  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.  
  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.  
  15. J. Honkala, A new bound for the D0L sequence equivalence problem. Acta Inform.43 (2007) 419–429.  
  16. J. Karhumäki, On the equivalence problem for binary D0L systems. Inform. Control50 (1981) 276–284.  
  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.  
  18. W. Magnus, On a theorem of Marshall Hall. Ann. Math.40 (1954) 764–768.  
  19. G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems. Academic Press (1980).  
  20. Handbook of Formal Languages. Vols. 1–3, edited by G. Rozenberg and A. Salomaa. Springer–Verlag (1997).  
  21. K. Ruohonen, Test sets for iterated morphisms. Mathematics Report No49. 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.  
  23. K. Ruohonen, Solving equivalence of recurrent sequences in groups by polynomial manipulation. Fund. Inform.38 (1999) 135–148.  
  24. K. Ruohonen, Explicit test sets for iterated morphisms in free monoids and metabelian groups. Theoret. Comput. Sci.330 (2005) 171 –191.  
  25. A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series. Springer–Verlag (1978).  
  26. W.M. Schmidt, The zero multiplicity of linear recurrence sequences. Acta Math.182 (1999) 243–282.  

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.