k -синхронизированная последовательность

Не путать с синхронизирующим словом .

В математике и теоретической информатике k - синхронизированная последовательность — это бесконечная последовательность термов s ( n ), характеризующаяся конечным автоматом, принимающим в качестве входных данных две строки m и n , каждая из которых выражена в некоторой фиксированной базе k , и допускающую условие m = s. ( н ). Класс k -синхронизированных последовательностей лежит между классами k -автоматических последовательностей и k -регулярных последовательностей .

Определения

Как отношения

Пусть Σ — алфавит из k символов, где k ≥ 2, и пусть [ n ] _k обозначает представление по основанию k некоторого числа n . Учитывая r ≥ 2, подмножество R из $\mathbb {N} ^{r}$ является k -синхронизированным, если отношение {([ n ₁ ] _k , ..., [ n _r ] _k )} является правосинхронизированным рациональное отношение над Σ ^∗ × ... × С ^∗ , где ( n ₁ , ..., n _r ) $\in$ Р. ​

Теоретико-языковый

Пусть n ≥ 0 — натуральное число и пусть f : $\mathbb {N} \rightarrow \mathbb {N}$ быть картой, где и n , и f ( n ) выражены в системе счисления k . Последовательность f ( n ) является k -синхронизированной, если язык пар $\{(n,f(n))\}$ является регулярным .

История

Класс k -синхронизированных последовательностей был введен Карпи и Магги.

Пример

Сложность подслова

Для заданной k -автоматической последовательности s ( n ) и бесконечной строки S = ​​s (1) s (2)... пусть ρS ₍ n) обозначает сложность подслова S ; то есть количество различных подслов длины n в S . Гоч, Шеффер и Шалит продемонстрировал, что существует конечный автомат, допускающий язык

$\{(n,m)_{k}\mid n\geq 0{\text{ and }}m=\rho _{S}(n)\}.$

Этот автомат угадывает конечные точки каждого смежного блока символов в S и проверяет, что каждое подслово длины n, начинающееся внутри данного блока, является новым, а все остальные подслова — нет. Затем он проверяет, что m является суммой размеров блоков. Поскольку пара ( n , m ) _k принимается этим автоматом, функция сложности подслова k -автоматической последовательности s ( n ) является k -синхронизированной.

Характеристики

k -синхронизированные последовательности обладают рядом интересных свойств. Неисчерпывающий список этих свойств представлен ниже.

• Любая k -синхронизированная последовательность является k -регулярной .
• Каждая k -автоматическая последовательность - синхронизирована k . Точнее, последовательность s ( n ) является k -автоматической тогда и только тогда, когда s ( n ) k -синхронизирована и s ( n ) принимает конечное число членов. Это является непосредственным следствием как вышеуказанного свойства, так и того факта, что каждая k -регулярная последовательность, принимающая конечное число членов, является k -автоматической.
• Класс k -синхронизированных последовательностей замкнут относительно почленной суммы и почленной композиции.
• Члены любой k -синхронизированной последовательности имеют линейную скорость роста.
• Если s ( n ) является k -синхронизированной последовательностью, то и сложность подслова s ( n ), и палиндромная сложность s ( n ) (аналогично сложности подслова, но для различных палиндромов ) являются k -регулярными последовательностями.

Ссылки

• Карпи, А.; Магги, К. (2010), «О синхронизированных последовательностях и их разделителях» , Теорет. Прикладная информатика. , 35 (6): 513–524, doi : 10.1051/ita:2001129 .