Локально периодические бесконечные частичные слова

Abstract

В работе изучаются бесконечные частичные слова с двумя локальными периодами и их специальные конечные подпоследовательности, наличие которых ведет к нарушению глобальных периодических закономерностей в бесконечном слове. Найдены необходимые и достаточные условия наличия в бесконечном слове специальных подпоследовательностей, построен полиномиальный алгоритм с конечной памятью для проверки этих условий.

An infinite partial word over an alphabet A is a partial function W; Z -» A. A partial word W has local period p if the equality W(i) = W(i + p) holds for all positions in the domain of W. In this paper we consider infinite partial words with two local periods and their special finite subsequences which make such partial words globally non-periodic. We provide necessary and sufficient conditions for the existence of a special subsequence in a given infinite partial word and give a polynomial constant-memory algorithm to check up these conditions.