کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952035 1442007 2017 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Prefix-suffix square reduction
ترجمه فارسی عنوان
کاهش مربع پیشوند-پسوند
کلمات کلیدی
تکثیر، پیش فاکتور، کاهش پسوند مربع، ریشه کاهش مربع اولیه، زبان رسمی،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this work we introduce the operation of prefix-suffix square reduction as the inverse of the prefix-suffix duplication studied in the literature. This operation reduces all possible squares that are prefixes or suffixes of a word to one half of these squares. Two variants are considered, depending on the unbounded and bounded length of the removed prefix or suffix. We investigate the complexity of the (non-uniform) membership problem for the prefix-suffix square reduction of a given language and the closure properties of some classes of languages under these operations as well as under their iterated variants. Afterwards, we define the primitive prefix-suffix square root of a word w as a word x that can be obtained from w by iterated prefix-suffix square reductions and it is irreducible in turn, i.e., no further prefix or suffix square reduction can be applied. We prove that the language of primitive prefix-suffix square roots of all words over an alphabet is never regular for alphabets with at least two symbols in the unbounded case, and always regular in the bounded case. The paper ends with a brief discussion on some open problems and some algorithmic aspects.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 682, 19 June 2017, Pages 49-56
نویسندگان
, , ,