کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875555 | 1441969 | 2018 | 23 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Quasi-periodic β-expansions and cut languages
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Motivated by the analysis of neural net models between integer and rational weights, we introduce a so-called cut language over a real digit alphabet, which contains finite β-expansions (i.e. base-β representations) of the numbers less than a given threshold. We say that an infinite β-expansion is eventually quasi-periodic if its tail sequence formed by the numbers whose representations are obtained by removing leading digits, contains an infinite constant subsequence. We prove that a cut language is regular iff its threshold is a quasi-periodic number whose all β-expansions are eventually quasi-periodic, by showing that altogether they have a finite number of tail values. For algebraic bases β, we prove that there is an eventually quasi-periodic β-expansion with an infinite number of tail values iff there is a conjugate of β on the unit circle. For transcendental β combined with algebraic digits, a β-expansion is eventually quasi-periodic iff it has a finite number of tail values. For a Pisot base β and digits from the smallest field extension Q(β) over rational numbers including β, we show that any number from Q(β) is quasi-periodic. In addition, we achieve a dichotomy that a cut language is either regular or non-context-free and we show that any cut language with rational parameters is context-sensitive.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 720, 11 April 2018, Pages 1-23
Journal: Theoretical Computer Science - Volume 720, 11 April 2018, Pages 1-23
نویسندگان
JiÅà ŠÃma, Petr Savický,