کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657007 | 687687 | 2005 | 28 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Insufficiency of four known necessary conditions on string unavoidability
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Insufficiency of four known necessary conditions on string unavoidability Insufficiency of four known necessary conditions on string unavoidability](/preview/png/9657007.png)
چکیده انگلیسی
The reductive decision procedure for unavoidable strings was recently shown to have an exponential lower bound. Hence, as a special case of generalized pattern matching, the existence of an efficient algorithm deciding string unavoidability remains an interesting open question. It has been hypothesized that some combination of the four necessary conditions implied by the known decidability results would be sufficient. Three of these criteria are determined in polynomial time, and the fourth provides the needed recursion. In this paper, however, we demonstrate the existence of arbitrarily many avoidable strings meeting any extended conjunction of the four necessary conditions. These insufficiency results are achieved by analyzing the appropriate graphical interpretations of the given algorithms. We provide a new combinatorial operation on the corresponding strings and generate arbitrary counterexamples from an empirically located minimal set. Thus, string unavoidability cannot be efficiently decided by the known reductive method or its immediate implications.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Algorithms - Volume 56, Issue 2, August 2005, Pages 96-123
Journal: Journal of Algorithms - Volume 56, Issue 2, August 2005, Pages 96-123
نویسندگان
Christine E. Heitsch,