کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777077 | 1632570 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On universal partial words
ترجمه فارسی عنوان
کلمات کلیدی جزئی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A universal word for a finite alphabet A and some integer nâ¥1 is a word over A such that every word of length n appears exactly once as a (consecutive) subword. It is well-known and easy to prove that universal words exist for any A and n. In this work we initiate the systematic study of universal partial words. These are words that in addition to the letters from A may contain an arbitrary number of occurrences of a special 'joker' symbol ââA, which can be substituted by any symbol from A. For example, u=0â011100 is a universal partial word for the binary alphabet A={0,1} and for n=3 (e.g., the first three letters of u yield the subwords 000 and 010). We present results on the existence and non-existence of universal partial words in different situations (depending on the number of âs and their positions), including various explicit constructions. We also provide numerous examples of universal partial words that we found with the help of a computer.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 231-237
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 231-237
نویسندگان
Herman Z.Q. Chen, Sergey Kitaev, Torsten Mütze, Brian Y. Sun,