کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
438393 690266 2008 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On stabilizers of infinite words
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On stabilizers of infinite words
چکیده انگلیسی

The stabilizer of an infinite word over a finite alphabet Σ is the monoid of morphisms over Σ that fix . In this paper we study various problems related to stabilizers and their generators. We show that over a binary alphabet, there exist stabilizers with at least n generators for all n. Over a ternary alphabet, the monoid of morphisms generating a given infinite word by iteration can be infinitely generated, even when the word is generated by iterating an invertible primitive morphism. Stabilizers of strict epistandard words are cyclic when non-trivial, while stabilizers of ultimately strict epistandard words are always non-trivial. For this latter family of words, we give a characterization of stabilizer elements.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 400, Issues 1–3, 9 June 2008, Pages 169-181