کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430957 | 688238 | 2012 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Periods in partial words: An algorithm
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Periods in partial words: An algorithm Periods in partial words: An algorithm](/preview/png/430957.png)
چکیده انگلیسی
Partial words are finite sequences over a finite alphabet that may contain some holes. A variant of the celebrated Fine–Wilf theorem shows the existence of a bound L=L(h,p,q)L=L(h,p,q) such that if a partial word of length at least L with h holes has periods p and q , then it also has period gcd(p,q)gcd(p,q). In this paper, we associate a graph with each p- and q-periodic word, and study two types of vertex connectivity on such a graph: modified degree connectivity and r -set connectivity where r=qmodp. As a result, we give an algorithm for computing L(h,p,q)L(h,p,q) in the general case and show how to use it to derive the closed formulas.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 16, October 2012, Pages 113–128
Journal: Journal of Discrete Algorithms - Volume 16, October 2012, Pages 113–128
نویسندگان
F. Blanchet-Sadri, Travis Mandel, Gautam Sisodia,