Periodicity Problem of Substitutions over Ternary Alphabets
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 42, Issue: 4, page 747-762
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topTan, Bo, and Wen, Zhi-Ying. "Periodicity Problem of Substitutions over Ternary Alphabets." RAIRO - Theoretical Informatics and Applications 42.4 (2010): 747-762. <http://eudml.org/doc/92901>.
@article{Tan2010,
abstract = {
In this paper, we characterize the substitutions over a
three-letter alphabet which generate a ultimately periodic
sequence.
},
author = {Tan, Bo, Wen, Zhi-Ying},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Periodicity; substitution.; periodicity; substitution},
language = {eng},
month = {3},
number = {4},
pages = {747-762},
publisher = {EDP Sciences},
title = {Periodicity Problem of Substitutions over Ternary Alphabets},
url = {http://eudml.org/doc/92901},
volume = {42},
year = {2010},
}
TY - JOUR
AU - Tan, Bo
AU - Wen, Zhi-Ying
TI - Periodicity Problem of Substitutions over Ternary Alphabets
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 42
IS - 4
SP - 747
EP - 762
AB -
In this paper, we characterize the substitutions over a
three-letter alphabet which generate a ultimately periodic
sequence.
LA - eng
KW - Periodicity; substitution.; periodicity; substitution
UR - http://eudml.org/doc/92901
ER -
References
top- N.J. Fine and H.S. Wilf, Uniqueness theorem for periodic functions. Proc. Amer. Math. Soc.16 (1965) 109–114.
- T. Harju and M. Linna, On the periodicity of morphisms on free monoids. RAIRO-Theor. Inf. Appl.20 (1986) 47–54.
- T. Head, Fixed languages and the adult language of 0L schemes. Int. J. Comput. Math.10 (1981) 103–107.
- B. Lando, Periodicity and ultimate periodicity of D0L systems. Theor. Comput. Sci.82 (1991) 19–33.
- M. Lothaire, Combinatorics on Words. Encyclopedia of Mathematics and its Applications, Vol. 17, Addison-Wesley (1983).
- J. Pansiot, Decidability of periodicity for infinite words. RAIRO-Theor. Inf. Appl.20 (1986) 43–46.
- G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems. Academic Press, New York (1980).
- P. Séébold, An effective solution to the D0L periodicity problem in the binary case. EATCS Bull.36 (1988) 137–151.
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.