A bound for the ω -equivalence problem of polynomial D0L systems

Juha Honkala

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

  • Volume: 37, Issue: 2, page 149-157
  • ISSN: 0988-3754

Abstract

top
We give a bound for the ω -equivalence problem of polynomially bounded D0L systems which depends only on the size of the underlying alphabet.

How to cite

top

Honkala, Juha. "A bound for the $\sf \omega $-equivalence problem of polynomial D0L systems." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 37.2 (2003): 149-157. <http://eudml.org/doc/244793>.

@article{Honkala2003,
abstract = {We give a bound for the $\omega $-equivalence problem of polynomially bounded D0L systems which depends only on the size of the underlying alphabet.},
author = {Honkala, Juha},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {infinite words; D0L systems; Infinite words; D0L systems.},
language = {eng},
number = {2},
pages = {149-157},
publisher = {EDP-Sciences},
title = {A bound for the $\sf \omega $-equivalence problem of polynomial D0L systems},
url = {http://eudml.org/doc/244793},
volume = {37},
year = {2003},
}

TY - JOUR
AU - Honkala, Juha
TI - A bound for the $\sf \omega $-equivalence problem of polynomial D0L systems
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2003
PB - EDP-Sciences
VL - 37
IS - 2
SP - 149
EP - 157
AB - We give a bound for the $\omega $-equivalence problem of polynomially bounded D0L systems which depends only on the size of the underlying alphabet.
LA - eng
KW - infinite words; D0L systems; Infinite words; D0L systems.
UR - http://eudml.org/doc/244793
ER -

References

top
  1. [1] K. Culik II and T. Harju, The ω -sequence equivalence problem for D0L systems is decidable. J. ACM 31 (1984) 282-298. Zbl0632.68078MR819139
  2. [2] K. Culik II and A. Salomaa, On infinite words obtained by iterating morphisms. Theoret. Comput. Sci. 19 (1982) 29-38. Zbl0492.68059MR664411
  3. [3] 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
  4. [4] J. Honkala, On infinite words generated by polynomial D0L systems. Discrete Appl. Math. 116 (2002) 297-305. Zbl0993.68077MR1878575
  5. [5] J. Honkala, Remarks concerning the D0L ω -equivalence problem. Intern. J. Found. Comput. Sci. 13 (2002) 769-777. Zbl1066.68059MR1945315
  6. [6] J. Honkala, The equivalence problem of polynomially bounded D0L systems – a bound depending only on the size of the alphabet. Theory Comput. Systems 36 (2003) 89-103. Zbl1039.68067
  7. [7] G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems. Academic Press, New York (1980). Zbl0508.68031MR561711
  8. [8] G. Rozenberg and A. Salomaa (Eds.), Handbook of Formal Languages, Vols. 1-3. Springer, Berlin (1997). Zbl0866.68057MR1469992
  9. [9] A. Salomaa, On exponential growth in Lindenmayer systems. Indag. Math. 35 (1973) 23-30. Zbl0267.68032MR317587

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.