Unavoidable Set: Extension and Reduction
Phan Trung Huy; Nguyen Huong Lam
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 33, Issue: 3, page 213-225
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topHuy, Phan Trung, and Lam, Nguyen Huong. "Unavoidable Set: Extension and Reduction." RAIRO - Theoretical Informatics and Applications 33.3 (2010): 213-225. <http://eudml.org/doc/221975>.
@article{Huy2010,
abstract = {
We give an explicit criterion
for unavoidability of word sets. We characterize extendible, finitely
and infinitely as well, elements in them. We furnish a reasonable upper
bound and an exponential lower bound on the maximum leghth of words
in a reduced unavoidable set of a
given cardinality.
},
author = {Huy, Phan Trung, Lam, Nguyen Huong},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Unavoidable set; reduced unavoidable set; extension; reduction.; word sets},
language = {eng},
month = {3},
number = {3},
pages = {213-225},
publisher = {EDP Sciences},
title = {Unavoidable Set: Extension and Reduction},
url = {http://eudml.org/doc/221975},
volume = {33},
year = {2010},
}
TY - JOUR
AU - Huy, Phan Trung
AU - Lam, Nguyen Huong
TI - Unavoidable Set: Extension and Reduction
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 33
IS - 3
SP - 213
EP - 225
AB -
We give an explicit criterion
for unavoidability of word sets. We characterize extendible, finitely
and infinitely as well, elements in them. We furnish a reasonable upper
bound and an exponential lower bound on the maximum leghth of words
in a reduced unavoidable set of a
given cardinality.
LA - eng
KW - Unavoidable set; reduced unavoidable set; extension; reduction.; word sets
UR - http://eudml.org/doc/221975
ER -
References
top- M.-P. Schützenberger, On the Synchronizing Properties of Certain Prefix Codes. Inform. and Control7 (1964) 23-36.
- A.V. Aho and M.J. Corasick, Efficient String Machines, an Aid to Bibliographic Research. Comm. ACM18 (1975) 333-340.
- A. Ehrenfeucht, D. Haussler and G. Rozengerg, On Regularity of Context-free Languages. Theoret. Comput. Sci.27 (1983) 311-332.
- Ch. Choffrut and K. CulikII, On Extendibility of Unavoidable Sets. Discrete Appl. Math.9 (1984) 125-137.
- L. Rosaz, Inventories of Unavoidable Languages and the Word-Extension Conjecture, to appear.
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.