Partial words and a theorem of Fine and Wilf revisited |
| |
Authors: | F Blanchet-Sadri Robert A Hegstrom |
| |
Affiliation: | Department of Mathematical Sciences, University of North Carolina, P.O. Box 26170 Greensboro, NC 27402-6170, USA |
| |
Abstract: | A word of length n over a finite alphabet A is a map from {0,…,n?1} into A. A partial word of length n over A is a partial map from {0,…,n?1} into A. In the latter case, elements of {0,…,n?1} without image are called holes (a word is just a partial word without holes). In this paper, we extend a fundamental periodicity result on words due to Fine and Wilf to partial words with two or three holes. This study was initiated by Berstel and Boasson for partial words with one hole. Partial words are motivated by molecular biology. |
| |
Keywords: | Combinatorial problems Words Formal languages |
本文献已被 ScienceDirect 等数据库收录! |
|