کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436186 | 689976 | 2007 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On critical exponents in fixed points of non-erasing morphisms
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Let Σ be an alphabet of size t, let f:Σ∗→Σ∗ be a non-erasing morphism, let be an infinite fixed point of f, and let be the critical exponent of . We prove that if is finite, then for a uniform f it is rational, and for a non-uniform f it lies in the field extension Q[r,λ1,…,λℓ], where r,λ1,…,λℓ are the eigenvalues of the incidence matrix of f. In particular, is algebraic of degree at most t. Under certain conditions, our proof implies an algorithm for computing .
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 376, Issues 1–2, 10 May 2007, Pages 70-88
Journal: Theoretical Computer Science - Volume 376, Issues 1–2, 10 May 2007, Pages 70-88