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
topHow 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.
- K. Culik II and A. Salomaa, On infinite words obtained by iterating morphisms. Theoret. Comput. Sci.19 (1982) 29-38.
- A. Ehrenfeucht and G. Rozenberg, Elementary homomorphisms and a solution of the D0L sequence equivalence problem. Theoret. Comput. Sci.7 (1978) 169-183.
- J. Honkala, On infinite words generated by polynomial D0L systems. Discrete Appl. Math.116 (2002) 297-305.
- J. Honkala, Remarks concerning the D0L ω-equivalence problem. Intern. J. Found. Comput. Sci.13 (2002) 769-777.
- 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.
- G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems. Academic Press, New York (1980).
- G. Rozenberg and A. Salomaa (Eds.), Handbook of Formal Languages, Vols. 1-3. Springer, Berlin (1997).
- A. Salomaa, On exponential growth in Lindenmayer systems. Indag. Math.35 (1973) 23-30.
NotesEmbed ?
topYou 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.