کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
434807 689805 2012 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Weakly unambiguous morphisms
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Weakly unambiguous morphisms
چکیده انگلیسی

A nonerasing morphism σ is said to be weakly unambiguous with respect to a word s if σ is the only nonerasing morphism that can map s to σ(s), i.e., there does not exist any other nonerasing morphism τ satisfying τ(s)=σ(s). In the present paper, we wish to characterise those words with respect to which there exists such a morphism. This question is nontrivial if we consider so-called length-increasing morphisms, which map a word to an image that is strictly longer than the word. Our main result is a compact characterisation that holds for all morphisms with ternary or larger target alphabets. We also comprehensively describe those words that have a weakly unambiguous length-increasing morphism with a unary target alphabet, but we have to leave the problem open for binary alphabets, where we can merely give some non-characteristic conditions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 448, 24 August 2012, Pages 21-40