کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9515489 | 1343458 | 2005 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Finite automata and pattern avoidance in words
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We say that a word w on a totally ordered alphabet avoids the word v if there are no subsequences in w order-equivalent to v. In this paper we suggest a new approach to the enumeration of words on at most k letters avoiding a given pattern. By studying an automaton which for fixed k generates the words avoiding a given pattern we derive several previously known results for these kind of problems, as well as many new. In particular, we give a simple proof of the formula (Electron. J. Combin. 5(1998) #R15) for exact asymptotics for the number of words on k letters of length n that avoids the pattern 12â¯(â+1). Moreover, we give the first combinatorial proof of the exact formula (Enumeration of words with forbidden patterns, Ph.D. Thesis, University of Pennsylvania, 1998) for the number of words on k letters of length n avoiding a three letter permutation pattern.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 110, Issue 1, April 2005, Pages 127-145
Journal: Journal of Combinatorial Theory, Series A - Volume 110, Issue 1, April 2005, Pages 127-145
نویسندگان
Petter Brändén, Toufik Mansour,