# A bound for the $\omega $-equivalence problem of polynomial D0L systems

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

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

## Access Full Article

top## Abstract

top## How to cite

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

## NotesEmbed ?

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