کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435712 | 689929 | 2015 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Generating square-free words efficiently
ترجمه فارسی عنوان
تولید کلمات بدون مربع موثر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
کلمه بدون مربع، کلمه تصادفی الگوریتمهای رشته
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study a simple algorithm generating square-free words from a random source. The source produces uniformly distributed random letters from a k -ary alphabet, and the algorithm outputs a (k+1)(k+1)-ary square-free word. We are interested in the “conversion ratio” between the lengths of the input random word and the output square-free word. For any k≥3k≥3 we prove the expected value of this ratio to be a constant and calculate it up to an O(1/k5)O(1/k5) term. For the extremal case of ternary square-free words, we suggest this ratio to have a constant expectation as well and conjecture its actual value from computer experiments.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 601, 11 October 2015, Pages 67–72
Journal: Theoretical Computer Science - Volume 601, 11 October 2015, Pages 67–72
نویسندگان
Arseny M. Shur,