کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420665 683968 2009 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Unbordered partial words
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Unbordered partial words
چکیده انگلیسی

An unbordered   word is a string over a finite alphabet such that none of its proper prefixes is one of its suffixes. In this paper, we extend the results on unbordered words to unbordered partial words. Partial words are strings that may have a number of “do not know” symbols. We extend a result of Ehrenfeucht and Silberger which states that if a word uu can be written as a concatenation of nonempty prefixes of a word vv, then uu can be written as a unique concatenation of nonempty unbordered prefixes of vv. We study the properties of the longest unbordered prefix of a partial word, investigate the relationship between the minimal weak period of a partial word and the maximal length of its unbordered factors, and also investigate some of the properties of an unbordered partial word and how they relate to its critical factorizations (if any).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 5, 6 March 2009, Pages 890–900
نویسندگان
, , , , ,