عنوان پایان‌نامه
برخی خصوصیات واژه های اتوماتیک
- رشته تحصیلی
- علوم کامپیوتر
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس علوم شماره ثبت: 5480;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 65834
- تاریخ دفاع
- ۲۳ تیر ۱۳۹۳
- دانشجو
- افشین امینی
- استاد راهنما
- مرتضی محمدنوری
- چکیده
- واژه‌های اتوماتیک (دنباله‌های اتوماتیک) یکی از مهمترین دسته واژه‌های مورد مطالعه در ترکیبیات واژگان است. تعریف‌های مختلف و معادلی از این واژه‌ها، یک نتیجه مهم درباره نمای بحرانی آنها و همچنین چند مسئله تصمیم‌پذیری در مورد این واژه‌ها توضیح داده خواهد شد. C- تجزیه وz-تجزیه این دسته از واژه‌ها، یک مسئله باز است و ظاهرا به جز $c$-تجزیه واژه تو-مورس، تجزیه دیگری از واژه‌های اتوماتیک مورد بررسی قرار نگرفته است. در این پایان‌نامهc-تجزیه و z-تجزیهبرخی واژه‌های اتوماتیک از جمله z-تجزیه واژه تو-مورس، واژه رودین-شاپیرو، دنباله داخلی واژه تازدن کاغذ، و دنباله داخلی واژه رودین-شاپیرو و همچنین c-تجزیه واژه رودین-شاپیرو و دنباله داخلی آن ارائه خواهد شد و برای بعضی واژه‌های تگ یکنواخت حدس‌هایی ارائه شده که صحت آنها برای پیشوندهایی به طول بزرگ از هر واژه بررسی شده است، و همچنین برای c-تجزیه و z-تجزیه تمام واژه‌های تگ یکنواخت حدسی مطرح شده است. کلمات کلیدی: واژه اتوماتیک، واژه یکنواخت، c-تجزیه، z-تجزیه، نمای بحرانی
- Abstract
- The set of Automatic Words (Automatic Sequences) is a major set of words studied in the subject of combinatorics of words. Several equivalent definitions of them, an important result of their Critical Exponent, and some of their decision problems are explained. C-factorization and z-factorization this group of words is an open problem. It seems that except for the c-factorization of Thue-Morse, there is no other factorization for other automatic words. In this thesis, c-factorization and z-factorization of some of them, such as z-factorization of Thue-Morse, Rudin-Shapiro, internal sequence of Papaer-folding, and internal sequence of Rudin-Shapiro, plus c-factorization of Rudin-Shapiro and its internal sequence are calculated and the relation between their elements are proved. In addition, for some uniform tag words some conjecture will be given. The validity of these conjectures are verified by long prefix of each word. And also, a conjecture for all uniform tag sequences is given. Keywords: Automatic Words, Uniform Words, c-factorization, z-factorization, Critical Exponent
