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.  Zbl0602.68066
  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
  3. J. Berstel and C. Reutenauer, Rational Series and Their Languages. Springer-Verlag (1988).  Zbl0668.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
  5. K. Čulik II and I. Friš, The decidability of the equivalence problem for D0L-systems. Inform. Control35 (1977) 20–39.  Zbl0365.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.  Zbl0586.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
  8. A. Ehrenfeucht and G. Rozenberg, On a bound for the D0L sequence equivalence problem. Theoret. Comput. Sci.12 (1980) 339–342.  Zbl0456.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 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.  Zbl0605.10007
  11. J. Honkala, A short solution for the HDT0L sequence equivalence problem. Theoret. Comput. Sci.244 (2000) 267–270.  Zbl0945.68104
  12. J. Honkala, A polynomial bound for certain cases of the D0L sequence equivalence problem. Theoret. Comput. Syst.34 (2001) 263–272.  Zbl0988.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.  Zbl1039.68067
  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.  Zbl1082.68051
  15. J. Honkala, A new bound for the D0L sequence equivalence problem. Acta Inform.43 (2007) 419–429.  Zbl1106.68060
  16. J. Karhumäki, On the equivalence problem for binary D0L systems. Inform. Control50 (1981) 276–284.  Zbl0497.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.  
  18. W. Magnus, On a theorem of Marshall Hall. Ann. Math.40 (1954) 764–768.  Zbl0022.31403
  19. G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems. Academic Press (1980).  Zbl0508.68031
  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).  Zbl0612.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.  
  23. K. Ruohonen, Solving equivalence of recurrent sequences in groups by polynomial manipulation. Fund. Inform.38 (1999) 135–148.  Zbl0935.68134
  24. K. Ruohonen, Explicit test sets for iterated morphisms in free monoids and metabelian groups. Theoret. Comput. Sci.330 (2005) 171 –191.  Zbl1078.68094
  25. A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series. Springer–Verlag (1978).  Zbl0377.68039
  26. W.M. Schmidt, The zero multiplicity of linear recurrence sequences. Acta Math.182 (1999) 243–282.  Zbl0974.11013

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.