کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4951239 1441198 2017 36 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The extended equation of Lyndon and Schützenberger
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The extended equation of Lyndon and Schützenberger
چکیده انگلیسی
Lyndon and Schützenberger (1962) [3] investigated for which values of ℓ,m, and n, the word-equations uℓ=vmwn have only periodic solutions. Following their result, we determine precisely the values of ℓ,m, and n for which the generalised Lyndon-Schützenberger word equationsu1⋯uℓ=v1⋯vmw1⋯wn, where ui∈{u,θ(u)} for all 1≤i≤ℓ, vj∈{v,θ(v)} for all 1≤j≤m, wk∈{w,θ(w)} for all 1≤k≤n, and θ is an antimorphic involution, have only θ-periodic solutions, i.e., u,v,w∈{t,θ(t)}⁎ for some word t. This answers completely an open problem by Czeizler et al. (2009) [22].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 85, May 2017, Pages 132-167
نویسندگان
, , , ,