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

RAIRO - Theoretical Informatics and Applications (2010)

- 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 ω-equivalence problem of polynomial D0L systems." RAIRO - Theoretical Informatics and Applications 37.2 (2010): 149-157. <http://eudml.org/doc/92719>.

@article{Honkala2010,

abstract = {
We give a bound for the ω-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},

keywords = {Infinite words; D0L systems.},

language = {eng},

month = {3},

number = {2},

pages = {149-157},

publisher = {EDP Sciences},

title = {A bound for the ω-equivalence problem of polynomial D0L systems},

url = {http://eudml.org/doc/92719},

volume = {37},

year = {2010},

}

TY - JOUR

AU - Honkala, Juha

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

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 37

IS - 2

SP - 149

EP - 157

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

LA - eng

KW - Infinite words; D0L systems.

UR - http://eudml.org/doc/92719

ER -

## References

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

## NotesEmbed ?

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