کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875388 | 1441947 | 2018 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Unary patterns under permutations
ترجمه فارسی عنوان
الگوهای انار تحت تغییرات
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
ترکیبیات بر روی کلمات، الگوهای قابل اجتناب، الگوها تحت تغییرات،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Thue characterized completely the avoidability of unary patterns. Adding function variables gives a general setting capturing avoidance of powers, avoidance of patterns with palindromes, avoidance of powers under coding, and other questions of recent interest. Unary patterns with permutations have been previously analysed only for lengths up to 3. Consider a pattern p=Ïi1(x)â¦Ïir(x), with râ¥4, x a word variable over an alphabet Σ and Ïij function variables, to be replaced by morphic or antimorphic permutations of Σ. If |Σ|â¥3, we show the existence of an infinite word avoiding all pattern instances having |x|â¥2. If |Σ|=3 and all Ïij are powers of a single morphic or antimorphic Ï, the length restriction is removed. For the case when Ï is morphic, the length dependency can be removed also for |Σ|=4, but not for |Σ|=5, as the pattern xÏ2(x)Ï56(x)Ï33(x) becomes unavoidable. Thus, in general, the restriction on x cannot be removed, even for powers of morphic permutations. Moreover, we show that for every positive integer n there exists N and a pattern Ïi1(x)â¦Ïin(x) which is unavoidable over all alphabets Σ with at least N letters and Ï morphic or antimorphic permutation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 743, 26 September 2018, Pages 72-82
Journal: Theoretical Computer Science - Volume 743, 26 September 2018, Pages 72-82
نویسندگان
James Currie, Florin Manea, Dirk Nowotka, Kamellia Reshadi,