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

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

Определения

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

Пусть Σ - алфавит k символы, где k ≥ 2, и пусть [п]_k обозначают основание-k представление некоторого числа п. Данный р ≥ 2, подмножество р из ${ Displaystyle mathbb {N} ^ {r}}$ является k-синхронизируется, если отношение {([п₁]_k, ..., [п_р]_k)} является правосинхронизированным^[1] рациональное отношение над Σ^∗ × ... × Σ^∗, куда (п₁, ..., п_р) ${ displaystyle in}$ р.^[2]

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

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

История

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

Пример

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

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

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

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

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

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

Каждый k-синхронизированная последовательность k-обычный.^[4]
Каждый k-автоматическая последовательность является k-синхронизированный. Если быть точным, последовательность s(п) является k-автоматически тогда и только тогда, когда s(п) является k-синхронизированный и s(п) принимает конечное число членов.^[5] Это является непосредственным следствием как указанного выше свойства, так и того факта, что каждый k-регулярная последовательность, состоящая из конечного числа членов, есть k-автоматический.
Класс k-синхронизированные последовательности замкнуты по почленной сумме и почленной композиции.^[6]^[7]
Условия любых k-синхронизированные последовательности имеют линейную скорость роста.^[8]
Если s(п) это k-синхронизированная последовательность, тогда как подсловная сложность s(п) и палиндромная сложность s(п) (аналогично подсловной сложности, но для разных палиндромы ) находятся k-регулярные последовательности.^[9]

Примечания

^ Frougny, C .; Сакарович, Дж. (1993), "Синхронизированные рациональные отношения конечных и бесконечных слов", Теорет. Comput. Sci., 108: 45–82, Дои:10.1016 / 0304-3975 (93) 90230-Q
^ ^а ^б Карпи и Магги (2010)
^ Goč, D .; Schaeffer, L .; Шаллит, Дж. (2013). Сложность подслова и k-синхронизация. Конспект лекций по информатике. 7907. Редакторы Béal MP., Carton O. Berlin: Springer. ISBN 978-3-642-38770-8.
^ Карпи и Магги (2010), Предложение 2.6
^ Карпи и Магги (2010), Предложение 2.8
^ Карпи и Магги (2010), Предложение 2.1
^ Карпи и Магги (2010), Предложение 2.2
^ Карпи и Магги (2010), Предложение 2.5
^ Carpi, A .; Д'Алонзо, В. (2010), "О факторах синхронизированных последовательностей", Теорет. Comput. Sci., 411 (44–46): 3932–3937, Дои:10.1016 / j.tcs.2010.08.005