کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419362 683793 2013 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Counting minimal semi-Sturmian words
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Counting minimal semi-Sturmian words
چکیده انگلیسی

A finite Sturmian   word ww is a balanced word over the binary alphabet {a,b}{a,b}, that is, for all subwords uu and vv of ww of equal length, ||u|a−|v|a|≤1||u|a−|v|a|≤1, where |u|a|u|a and |v|a|v|a denote the number of occurrences of the letter aa in uu and vv, respectively. There are several other characterizations, some leading to efficient algorithms for testing whether a finite word is Sturmian. These algorithms find important applications in areas such as pattern recognition, image processing, and computer graphics. Recently, Blanchet-Sadri and Lensmire considered finite semi-Sturmian words of minimal length and provided an algorithm for generating all of them using techniques from graph theory. In this paper, we exploit their approach in order to count the number of minimal semi-Sturmian words. We also present some other results that come from applying this graph theoretical framework to subword complexity.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issue 18, December 2013, Pages 2851–2861
نویسندگان
, ,