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

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