کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435712 689929 2015 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Generating square-free words efficiently
ترجمه فارسی عنوان
تولید کلمات بدون مربع موثر
کلمات کلیدی
کلمه بدون مربع، کلمه تصادفی الگوریتمهای رشته
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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
نویسندگان
,