Long unavoidable patterns |
| |
Authors: | Ursula Schmidt |
| |
Affiliation: | (1) Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6980, D-7500 Karlsruhe 1, Federal Republic of Germany |
| |
Abstract: | Summary We examine long unavoidable patterns, unavoidable in the sense of Bean, Ehrenfeucht, McNulty. Zimin and independently Schmidt have shown that there is only one unavoidable pattern of length 2
n
-1 on an alphabet with n letters; this pattern is a quasi-power in the sense of Schützenberger. We characterize the unavoidable words of length 2
n
-2 and 2
n
-3. Finally we show that every sufficiently long unavoidable word has a certain quasi-power as a subword.This work was done while the author stayed at LITP, Université Paris 6, France |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|