Алгоритмические свойства последовательностей, близких к периодическим тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

|Ь

/

Московский государственный университет имени М. В. Ломоносова Механико-математический факультет

Алгоритмические свойства последовательностей, близких к периодическим

специальность 01.01.06 — математическая логика, алгебра и теория чисел

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

На правах рукописи УДК 510.5+519.1

Притыкин Юрий Львович

Москва — 2009

1 7 гг'л

003476633

Работа выполнена на кафедре математической логики и теории алгоритмов Механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

Научный руководитель: Официальные оппоненты:

Ведущая организация:

член-корреспондент РАН, профессор Семёнов Алексей Львович

доктор физико-математических наук, профессор Волков Михаил Владимирович

кандидат физико-математических наук Вялый Михаил Николаевич

Институт математики имени Л. С. Соболева СО РАН

Защита диссертации состоится 2 октября 2009 г. в 16 ч. 45 мин. на заседании диссертационного совета Д.501.001.84 при МГУ имени М. В. Ломоносова по адресу: РФ, 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, Механико-математический факультет, ауд. 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 2 сентября 2009 г.

Ученый секретарь

диссертационного совета /

Д.501.001.84 при МГУ 9 п Л^^

доктор физико-математических наук, / профессор / А. О. Иванов

Общая характеристика работы

Актуальность темы

Впервые почти периодические последовательности были рассмотрены в связи с символической динамикой. Продолжал и ссылаясь на работы Адамара и Пуанкаре, Морс в 1921 году опубликовал работу1, в которой определил почти периодические последовательности (он называл их рекуррентными). В 1938 — 1940 годах вышли работы Морса и Хедлунда "Символическая динамика"2,3, в которых многие свойства почти периодических последовательностей были подробно исследованы.

Последовательность символов конечного алфавита почти периодическая, если для каждого конечного подслова и последовательности найдётся такое натуральное число п, что в каждом подслове длины п последовательности найдётся вхождение слова и.

Определение почти периодической последовательности в достаточной степени является комбинаторным. Комбинаторные результаты появляются уже в работах Морса и Хедлунда. Кроме того, конечные и бесконечные слова и до этого изучались с комбинаторной точки зрения. Зарождением соответствующей области — комбинаторики слов — принято считать работы Туэ 1906 и 1912 годов4'5, в которых он, в частности, изучает свойства последовательности, теперь называемой последовательность Туэ — Морса, и доказывает её бескубность. Отметим, что Туэ не имел в виду каких-то конкретных применений своих результатов и считал рассматриваемые им вопросы представляющими самостоятельный интерес6. Сейчас комбинаторика слов — активная область, И в настоящей работе к ней можно отнести многие результаты.

lM. Morse. Recurrent geodesies on a surface of negative curvature. Transactions of the American Mathematical Society, 22:84-100,1921.

2M. Morse, G. A. Hedlund. Symbolic dynamics. American Journal of Mathematics, 60(4):815-866, 1938.

3M. Morse, G. A. Hedlund. Symbolic dynamics ii: Sturmian trajectories. American Journal of Mathematics, 62(l):l-42, 1940.

4A. Thue. Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. In Selected mathematical papers of Axel Thue, pp. 413-478. Oslo, Norway: Universitetsforlaget, 1977.

5A. Thue. Uber unendliche Zeichenreihen. In Selected mathematical papers of Axel Thue, pp. 139-158. Oslo, Norway: Universitetsforlaget, 1977.

6J.-P. Allouche, J. Shallit. The ubiquitous Prouhet-Thue-Morse sequence. In Sequences and their applications, Proceedings of SETA'98, pp. 1-16, Springer-Verlag, 1999.

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

Интересно, что свойства типа почти периодичности полезны и, более того, естественно возникают при решении такого типа задач. Следующее понятие было введено Семёновым7. Назовём последовательность обобщённо почти периодической, если каждое конечное слово либо входит в неё бесконечное количество раз с ограниченными интервалами между соседними вхождениями, либо входит лишь конечное количество раз. Будем называть последовательности, некоторый суффикс которых почти периодичен, заключительно почти периодическими. Заметим, что естественное предположение о том, что обобщённо почти периодические последовательности исчерпываются заключительно почти периодическими, оказывается неверным8.

В работе Бюхи 1962 года9 была доказана разрешимость теории MT(N, <} — монадической теории натуральных чисел с отношением порядка, при помощи сопоставления формул теории конечным автоматам на бесконечных последовательностях.

После этого возникает естественный вопрос о разрешимости теорий вида MT(N, <,х), то есть MT{N, <), расширенной некоторой последовательностью х. Конечно, теория MT(N, <, х) разрешима, если последовательность х выразима в исходной теории, но запас таких последовательностей невелик — это периодические последовательности, возможно, с предпериодом. Оказывается, что можно получить критерий разрешимости теории MT(N, <,х), если ограничиться рассмотрением обобщённо

7 A. JI. Семёнов. О некоторых расширениях арифметики сложения натуральных чисел. Известия АН СССР, серия математическая, 43(5):1175—1195, 1979.

8Ю. Л. Притыкин. Конечно-автоматные преобразования строго почти периодических последовательностей. Математические заметки, 80(5):751-756, 2006.

8 J. R. Biichi. On a decision method in restricted second-order arithmetic. In Proceedings of International Congress for Logic, Methodology and Philosophy of Science, pp. 1-11. Stanford University Press, 1962.

почти периодических последовательностей.

Пусть последовательность х обобщённо почти периодическая. Аналогом периода и предпериода для таких последовательностей является регулятор почти периодичности. Регулятором почти периодичности последовательности х называется такая функция R^: N —> N, которая на числе п равна минимальному такому что всякое слово длины п, входящее в х конечное количество раз, может входить только в начальный отрезок х длины I и не может входить далее, а также каждое слово длины п, входящее в х бесконечно много раз, входит в каждый отрезок длины I. Назовём последовательность эффективно обобщённо почти периодической, если она является вычислимой обобщённо почти периодической последовательностью, и некоторая оценка сверху на регулятор почти периодичности этой последовательности вычислима. Как доказал Семёнов10, теория MT{N, <,х) обобщённо почти периодической последовательности х разрешима тогда и только тогда, когда х эффективно обобщённо почти периодична.

Для доказательства этого результата необходимо разобраться в том, как ведёт себя конечный автомат, на вход которому подаётся обобщённо почти периодическая последовательность. Этот вопрос связан со следующей серией вопросов — понять, как меняются или насколько сохраняются различные свойства последовательностей при применении к ним различного вида преобразований. Естественно рассматривать простейшие алгоритмические преобразования — конечно-автоматные, то есть осуществляемые машиной с конечной памятью.

Основным средством в получении вышеприведённого критерия разрешимости монадических теорий обобщённо почти периодических последовательностей стал результат о сохраняемости множества обобщённо почти периодических последовательностей при конечно-автоматных преобразованиях, а также эффективная его версия, дающая оценку на регулятор образа при имеющемся регуляторе исходной последовательности10,11.

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

10А. JI. Семёнов. Логические теории одноместных функций на натуральном ряде. Известия АН СССР, серия математическая, 47(3):623-658, 1983.

11 An. Muchnik, A. Semenov, М. Ushakov. Almost periodic sequences. Theoretical Computer Science, 304(l-3):l-33, 2003.

известно12, что класс автоматных последовательностей (см. ниже) сохраняется под действием равномерных конечно-автоматных преобразований. Под равномерными мы понимаем такие конечно-автоматные преобразования, которые, получив на вход букву, всегда выдают на выход ровно одну букву. Морфические последовательности (см. ниже) также сохраняются под действием конечно-автоматных преобразований13.

Таким образом, представляется естественным более детально изучить свойства замкнутости классов последовательностей с различными свойствами типа почти периодичности относительно конечно-автоматных преобразований.

Другие важные для нас классы последовательностей, обладающих свойствами, близкими к свойствам периодических последовательностей, — это классы автоматных и морфических последовательностей.

Любая периодическая последовательность может быть порождена машиной с конечной памятью — достаточно иметь информацию о пред-периоде и периоде последовательности. И наоборот, любая машина с конечной памятью, печатающая символы конечного алфавита, порождает заключительно периодическую последовательность. Действительно, во время её работы в какой-то момент конфигурация машины полностью совпадёт с какой-то из уже встречавшихся, и так начнётся период в выходной последовательности. Если разрешить машине обращаться к символам, написанным ранее, класс порождаемых последовательностей существенно возрастёт. При некоторых ограничениях на порядок, в котором ранее написанные символы читаются снова, мы получим класс автоматных последовательностей, введённый Кобхэмом12.

Формально определим автоматные последовательности двумя эквивалентными способами.

Рассмотрим конечный автомат, действующий на словах в алфавите £*;= {0,1,..., А; - 1}. Каждому состоянию автомата соответствует буква в некотором другом алфавите А (разным состояниям могут соответствовать одинаковые буквы). Автомат действует так: получает на вход слово в алфавите £*., производит вычисления и выдаёт ту букву алфавита А, которая соответствует последнему состоянию в вычислении. Последовательность х букв алфавита А называется к-автоматпной, если

1SA. Cobham. Uniform tag sequences. Mathematical Systems Theory, 6:164-192,1972.

l3F. M. Dekking. Iteration of maps by an automaton. Discrete Mathematics, 126(1-3):81—86, 1994.

существует конечный автомат вышеуказанного вида, который, будучи запущенным на числе п, записанном в fc-ичной системе счисления, выдаёт букву х(п). Когда ясно или неважно, о каком к идёт речь, приставку "к-п мы будем опускать.

Теперь опишем другой подход. Пусть А, В — конечные алфавиты. Рассмотрим операцию подстановки, которая каждую букву алфавита А отображает в слово алфавита В. Результатом применения подстановки к конечному слову или бесконечной последовательности в алфавите А будет конкатенация образов букв, составляющих это слово или последовательность. Такие отображения подстановки называются морфизма-ми. Морфизм называется к-равномерным, если длины образов всех букв совпадают и равны к. Морфизм кестирающий, если образы всех букв непусты.

Ограничимся теперь рассмотрением ситуации, когда алфавиты Aw. В совпадают. Нас интересуют бесконечные последовательности, являющиеся неподвижными точками морфизмов, причём неподвижными точками достаточно общего вида. Пусть ф — морфизм в алфавите А, и s — буква алфавита А, такая что слово ф(з) начинается с s. Будем итерировать ф на s, получим слова s, ф{в), <^2(s), ф3(з), (¿>4(s), ..., каждое из которых начинается с предыдущего. Если длина слова <£n(s) стремится к бесконечности с ростом п, можно корректно определить бесконечную последовательность ф°°(з), началами которой являются слова </>n(s) для любого п. Последовательности х — которые можно получить

таким способом, называются чисто морфическими. Несложно видеть, что чисто морфическая последовательность, порождённая морфизмом ф, является неподвижной точкой под действием этого морфизма. Последовательности, получающиеся из чисто морфических отождествлением некоторых символов, называются морфическими. Как доказал Кобхэм12, fc-автоматные последовательности — это в точности морфические последовательности, полученные из порождённых fc-равномерными морфиз-мами чисто морфических последовательностей.

Морфические последовательности, точнее, тесно связанные с ними DOL-последовательности и, более общо, L-системы (системы Линден-майера), впервые появились в работах математика и биолога Линден-майера для описания процессов развития живых организмов14. Однако

14G. Rozenberg, A. Salomaa, editors. Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology, Springer-Verlag,

впоследствии морфические последовательности стали рассматриваться и в теории динамических систем, комбинаторике слов, теоретической информатике15,16,17. Автоматные последовательности неявно были впервые рассмотрены в работе Бюхи о связях монадических теорий и конечных автоматов18, первой работой, посвящённой их систематическому изучению, была работа Кобхэма12.

Множества морфических и почти периодических последовательностей находятся в общем положении. Заметим также, что морфические последовательности можно конечно описать — для этого нужно описать алфавит, морфизм, букву, на которой итерируется морфизм, и последующий способ отождествления букв в чисто морфической последовательности. Поэтому можно ставить алгоритмические вопросы о морфических последовательностях. Довольно естественным является вопрос о существовании алгоритма для следующей проблемы.

Проблема распознавания почти периодичности морфических последовательностей (ППМ):

Дано: конечное описание морфической последовательности, Определить: является ли эта последовательность почти периодической.

Многие алгоритмические задачи, связанные с морфизмами, являются довольно сложными и интересными16. Один из самых известных примеров такой задачи — проблема соответствий Поста (Post correspondence problem), которая неразрешима19,16. Про проблему ППМ до сих пор неизвестно, является ли она разрешимой, хотя гипотеза о разрешимости является довольно правдоподобной. В связи с этим представляется интересным исследовать некоторые частные случаи проблемы ППМ, возникающие при ограничении множества входов на морфические последовательности специального вида.

__

15 J.-P. Allouche, J. Shallit. Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, 2003.

1ST. Harju, J. Karhumäki. Morphisms. In G. Rozenberg, A. Salomaa, editors, Handbook of formal languages, vol. 1, pp. 439-510, Springer-Verlag, 1997.

l7M. Queffelec. Substitution Dynamical Systems—Spectral Analysis, Lecture Notes in Mathematics, vol. 1284, Springer-Verlag, 1987.

18J. R. Büchi. Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math., 6:66-92, 1960.

19M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company: Boston, 2nd edition, 2005.

Тесто связанный с проблемой ППМ вопрос или даже вариант формулировки — получение по возможности как можно более компактного и эффективно проверяемого критерия почти периодичности для морфи-ческих последовательностей. Вопрос о получении такого критерия для чисто морфических последовательностей был поставлен как открытый в монографии Аллуша и Шаллита15, раздел 10.12, проблема 5.

Одной из простейших и наиболее естественных характеристик бесконечных последовательностей является их подсловная сложность. Под-словной сложностью последовательности х называется такая функция P: N —» N, что р(п) равно количеству слов длины п, входящих в последовательность х. Для последовательностей в алфавите из m символов подсловная сложность может варьироваться от 1 до m". Как доказано в работе Морса и Хедлунда2, подсловная сложность последовательности ограничена тогда и только тогда, когда последовательность является заключительно периодической.

Асимптотическое поведение подсловной сложности бесконечных последовательностей широко изучалось, в том числе и в контексте теории динамических систем20,21. В серии работ, завершающейся работой Пансио 1984 года22, доказано, что подсловная сложность чисто морфиче-ской последовательности может удовлетворять одной из пяти следующих асимптотик: 0(1), 6(п), 6(nloglogn), О (n Iogn), © (n2). В работе Пансио 1985 года23 показано, что существуют примеры морфических последовательностей с подсловной сложностью вида 9(п1+*) для каждого к € N. После этого про подсловную сложность морфических последовательностей произвольного вида долгое время не было известно ничего нового. Наконец, Девятовым было доказано24, что подсловная сложность морфи-

20J.-P. Allouche. Sur la complexité des suites infinies. Bulletin of the Belgian Mathematical Society—Simon Stevin, 1(2):133-143, 1994.

21S. Ferenczi. Complexity of sequences and dynamical systems. Discrete Mathematics, 206( 1) : 145—154, 1999.

22J.-J. Pansiot. Complexité des facteurs des mots infinis engendrés par morphismes itérés. In Proceedings of the 11th International Colloquium on Automata, Languages, and Programming (ICALP'84), Antwerp, Belgium, Lecture Notes in Computer Science, vol. 172, pp. 380-389, Springer-Verlag, 1984.

23J.-J. Pansiot. Subword complexities and iteration. Bulletin of the European Association for Theoretical Computer Science, 26:55-62, 1985.

24 R. Devyatov. On subword complexity of morphic sequences. In Proceedings of the 3rd International Computer Science Symposium in Russia (CSR 2008), Moscow, Russia, Lecture Notes in Computer Science, vol. 5010, pp. 146-157, Springer-Verlag, 2008.

ческой последовательности имеет один из следующих видов: O(nlogn) или для некоторого к € N. Таким образом, для полного описания

возможных асимптотик подсловной сложности морфической последовательности осталось разобраться подробнее со случаем O(nlogn).

В случае автоматных последовательностей ситуация существенно проще: подсловная сложность автоматной последовательности не более чем линейна12.

Несложно показать, что подсловная сложность почти периодической последовательности в алфавите из m символов не может быть больше тап для некоторого фиксированного а < 121. При этом можно показать, что для любого ß < 1 существует почти периодическая последовательность в алфавите из m символов с подсловной сложностью не меньше

mßn 25_

Оказывается, подсловная сложность последовательности, являющейся одновременно морфической и почти периодической, устроена гораздо проще. Как мы доказываем в настоящей работе, подсловная сложность таких последовательностей не более чем линейна. Отметим, что линейность подсловной сложности почти периодических чисто морфических последовательностей была известна ранее17.

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

Периодические последовательности имеют самую простую структуру среди всех последовательностей над конечным алфавитом, поэтому естественно было бы научиться измерять, насколько данная последовательность далека от любой периодической. Мы вводим26 понятие меры апериодичности бесконечной последовательности. Неформально, мера апериодичности последовательности — это максимальное такое число а, что последовательность с любым своим нетривиальным сдвигом имеет хотя бы долю а различий. Насколько известно автору, систематического исследования этого понятия и его свойств ранее не проводилось, извест-

25Yu. Pritykin. Information in infinite words. In Proceedings of the 6th International Conference on Words (Words 2007), Marseille, France, pp. 254-261. Institute de Mathématiques de Luminy, Marseille, FVance, 2007.

2S Yu. Pritykin, J. Ulyashkina. Aperiodicity measure for infinite sequences. In Proceedings of the 4th International Computer Science Symposium in Russia (CSR 2009), Novosi-

birsk, Russia, Lecture Notes in Computer Science, vol. 5675, pp. 274-285. Springer-Verlag, 2009.

ны только некоторые отдельные результаты. Мы получаем некоторые простейшие свойства и вычисляем меру апериодичности некоторых конкретных последовательностей.

Цель работы

1) Изучение свойств замкнутости различных классов последовательностей со свойствами типа почти периодичности относительно действия конечно-автоматных преобразований;

2) исследование возможностей эффективного распознавания и вычисления свойств и характеристик последовательностей со свойствами типа почти периодичности;

3) получение эффективных алгоритмов разрешения свойства почти периодичности для некоторых подклассов класса морфических последовательностей;

4) изучение поведения подсловной сложности последовательностей, являющихся одновременно почти периодическими и морфическими;

5) изучение простейших свойств понятия меры апериодичности бесконечной последовательности.

Основные методы исследования

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

Научная новизна

Результаты работы являются новыми и состоят в следующем.

1) Доказано, что классы заключительно почти периодических и заключительно рекуррентных последовательностей сохраняются под действием конечно-автоматных преобразований.

2) Получена оценка сверху на длину конечного слова, которое достаточно отрезать от образа почти периодической последовательности под действием конечно-автоматного преобразования, чтобы получить почти периодическую последовательность.

3) Доказано, что по обобщённо почти периодической последовательности и её регулятору почти периодичности невозможно распознать,

является ли последовательность заключительно почти периодической, и получены другие результаты о невычислимости некоторых свойств обобщённо почти периодических последовательностей.

4) Получены полиномиальные по времени работы алгоритмы, определяющие по автоматной или чисто морфической последовательности, полученной из нестирающего морфизма, является ли эта последовательность почти периодической.

5) Доказано, что подсловная сложность морфической почти периодической последовательности не более чем линейна.

6) Доказаны простейшие свойства меры апериодичности бесконечных последовательностей и вычислены значения меры апериодичности для некоторых хорошо известных последовательностей.

Теоретическая и практическая ценность

Работа носит теоретический характер. Результаты диссертации могут быть использованы при дальнейшем изучении свойств почти периодических, морфических и автоматных последовательностей.

Апробация результатов

Результаты работы докладывались на следующих научно-исследовательских семинарах и научных конференциях.

• Колмогоровский семинар кафедры математической логики и теории алгоритмов под руководством профессора Н. К. Верещагина, к. ф.-м. н. А. Е. Ромащенко, члена-корреспондента РАН, профессора А. Л. Семёнова, к. ф,-м. н. А. Шеня, 2006 — 2009 гг.

• Семинар "Алгоритмические вопросы алгебры и логики" под руководством академика РАН С. И. Адяна, 2006 — 2007 гг.

• Научно-исследовательский семинар кафедры математической логики и теории алгоритмов под руководством академика РАН С. И. Адяна, члена-корреспондента РАН Л. Д. Беклемишева и профессора В. А. Успенского, 2009 г.

• XXVIII Конференция молодых учёных, механико-математический факультет МГУ им. М. В. Ломоносова, 2006 г.

• Семинар по словам и автоматам в рамках 1-го международного симпозиума по компьютерным наукам в России, Санкт-Петербург, 2006 г.

• Workshop on Algorithms on Words, Турку, Финляндия, 2007 г.

• International Conference "Automata: from Mathematics to Applications" (AutoMathA 2007), Палермо, Италия, 2007 г.

• 11-th International Conference "Developments in Language Theory" (DLT 2007), Турку, Финляндия, 2007 г.

• Семинар по словам, автоматам и динамике в рамках 2-го международного симпозиума по компьютерным наукам в России, Екатеринбург, 2007 г.

• 6-th International Conference on Combinatorics on Words (Words 2007), Марсель, Франция, 2007 г.

• Конференция "Фундаментальная математика в работах молодых учёных", посвягцённая десятилетию всероссийского конкурса Мёбиуса математических работ, Москва, 2007 г.

Публикации

Основные результаты диссертации опубликованы в 6 работах автора, список которых приведён в конце автореферата [1-6].

Структура и объем диссертации

Диссертация состоит из 6 глав и списка литературы. Полный объём диссертации — 96 страниц, список цитируемой литературы содержит 48 наименований.

Краткое содержание работы

Глава 1 является введением диссертации. Во введении описываются цели и задачи работы, обосновывается её актуальность и научная новизна.

В главе 2 вводятся необходимые понятия и обсуждаются их основные свойства.

Для конечного алфавита А через А* обозначим множество всех слов, а через j4n множество всех последовательностей в этом алфавите. Подсло-ва последовательности х вида х[0,г] называются префиксами х, последовательности вида x(i)x(i+l)x(i+2)... — суффиксами х и обозначаются x[i, оо). Через |и| будем обозначать длину слова и.

Последовательность х называется почти периодической, если для каждого её подслова и найдётся такое натуральное I, что на каждом отрезке длины I последовательности х найдётся вхождение слова и. Тем самым, любое слово, входящее в почти периодическую последовательность, входит в неё бесконечное количество раз. Будем называть последовательность х заключительно почти периодической, если некоторый её суффикс почти периодичен. Последовательность х называется обобщённо почти периодической, если для каждого её подслова и, входящего в неё бесконечное число раз, найдётся такое натуральное I, что на каждом отрезке длины I последовательности х найдётся вхождение слова и. Отметим, что множество заключительно почти периодических последовательностей является собственным подмножеством множества обобщённо почти периодических последовательностей.

Регулятором почти периодичности обобщённо почти периодической последовательности х назовём функцию И®: N —» Н, которая на числе п равна минимальному такому I, что каждое слово длины п, которое входит в х бесконечное количество раз, встретится на любом отрезке длины I последовательности х, а также любое слово длины п, которое входит в х конечное количество раз, не входит в х[1, оо). Часто вместо регулятора достаточно рассматривать только какую-то верхнюю оценку на него, то есть функцию /: N —► К, такую что /(п) > ^(п) для всех п — в этом случае пишут / ^Кх.

Пусть А, В — конечные алфавиты. Отображение ф: А* —» В* называется морфизмом, если для любых и, V € А* выполнено ф(иь) = ф(и)ф{и). Ясно, что морфизм полностью определяется своими значениями на од-нобуквенных словах. Морфизм нестираюгций, если |<^(а)| > 1 для всех а е А. Морфизм называется к-равномерным, если |$(а)| = к для всех о 6 Л. 1-равномерный морфизм называется кодированием. Естественным образом морфизмы продолжаются на бесконечные последовательности: если х — последовательность букв алфавита А, по определению положим ф(х) = 0(ж(О))0(х(1))0(х(2)) ...

Пусть ф: А* —> А* — некоторый морфизм, и пусть ф(з) = ей для некоторых 5 € А, и € Л*. Тогда для всех натуральных т < п слово фп(з) начинается со слова фт(я), так что можно корректно определить

= Итп—оо Фп(3) — зиф(и)ф2(и)ф3(и)____Если фп{и) ф А для всех п,

то </>°°(з) бесконечна. В этом случае говорят, что морфизм ф продолжаем на а. Последовательности вида Ь(ф°°(в))> где Н: А —> В — кодирование, называются морфическими, вида ф"х(з) — чисто морфическими.

Последовательности вида Н(ф°°(з)), где Ь: А —+ В — кодирование, а ф — ^-равномерный морфизм, называются к-автоматными. Когда ясно или неважно, о каком к идёт речь, приставку опускают.

Конечно-автоматным преобразователем назовём совокупность М = {А, В, <5, д, А, ¡л), где А и В — конечные множества, называемые соответственно входной и выходной алфавит, <Э — конечное множество состояний, ^ € <5 — выделенное состояние, называемое начальным, и

А:<2хЛ-*£*, ¿г: <2 хЛ —<2

— функции переходов. Функции переходов можно естественным обрат зом продолжить на <3 х А* по индукции: ^(д. иа) = и), а) и

Л(<7, иа) = Х(д,и)Х({1(д,и),а) для д £ <Э, и е А*, такого что и ф Л, и а € Л.

Пусть х € Лг\ Последовательность о элементов множества <3 назовём ходом преобразователя М на х, если ро = д и для каждого п выполняется рп+1 = д(рп, х(п)). Ясно, что ход существует и единствен. Последовательность М(х), определяемую как М(х)(п) — Х(рп,х(п)), где (Рп)п=о — ход преобразователя М над;, назовём образом последовательности х под действием М.

Если для каждых а 6 А, 6 С} выполнено |А(д, а)| = 1, то преобразователь М называется равномерным. Несложно видеть, что применение произвольного конечно-автоматного преобразователя к последовательности можно представить как последовательное применение равномерного конечно-автоматного преобразователя и некоторого морфизма. Поэтому часто для упрощения ситуации мы ограничиваемся рассмотрением равномерных конечно-автоматных преобразователей. Если [г, — вхождение слова и в последовательность х, причём р* = д, где (рп)£10 — ход преобразователя М на х, то будем говорить, что преобразователь М подходит к этому вхождению слова и в состоянии д.

Назовём конечно-автоматный преобразователь М = {А, В, Сд, А, ц) обратимым, если для каждых д € <5 и а € А существует ровно одно состояние д' 6 <3, такое что а) = д. Другими словами, в таком преобразователе каждая буква входного алфавита осуществляет взаимно однозначное отображение множества состояний в себя. Находясь в некотором состоянии и зная последовательность предыдущих входных символов, можно восстановить и последовательность пройденных состояний (в этом и заключается свойство обратимости).

Лодсловной сложностью последовательности х называется такая функция Рх: N —► Н, что Рх(п) равно количеству слов длины п, входящих в последовательность х.

В последующих главах излагаются результаты диссертации.

Глава 3 посвящена конечно-автоматным преобразованиям. Из теоремы Семёнова следует, что образ почти периодической последовательности под действием конечно-автоматного преобразования является обобщённо почти периодической последовательностью. Оказывается, верно более сильное утверждение.

Теорема 1. Почти периодические последовательности под действием конечно-автоматных преобразований переходят в заключительно почти периодические.

Рассмотрим такой вопрос об эффективизации теоремы 1. Допустим, нам известны конечно-автоматный преобразователь, почти периодическая последовательность и оценка на её регулятор почти периодичности. В соответствии с теоремой 1 от образа этой последовательности под действием этого преобразователя можно отрезать некоторый начальный отрезок, так что получится почти периодическая последовательность. Можно ли оценить сверху длину этого отрезка? Ан. А. Мучник в 2005 г. высказал гипотезу о том, что это невозможно сделать эффективно, однако результат следующей теоремы 2 показывает, что такая оценка существует. Для произвольной функции д: N —► N обозначим о о д о • ■ • о д через дт.

V

т

Теорема 2. Пусть М —равномерный конечно-автоматный преобразователь с т состояниями, их — почти периодическая последовательность. Тогда образ х под действием М становится почти периодической последовательностью при удалении префикса длиной не более

И5Ч1) + ИГ1(1) + ••• + 1^(1).

Одним из основных шагов в доказательстве теоремы 2, представляющим и самостоятельный интерес, является следующий результат.

Предложение 3. Почти периодические последовательности под действием обратимых конечно-автоматных преобразований переходят в почти периодические.

Далее мы доказываем замкнутость относительно конечно-автоматных преобразований для рекуррентных последовательностей, а также относительно почти обратимых конечно-автоматных преобразований для обобщённо почти периодических последовательностей. Мы доказываем, однако, что множество обобщённо почти периодических последовательностей не замкнуто относительно более широкого класса стековых конечно-автоматных преобразований.

Глава 4 посвящена вопросам вычислимости на бесконечных последовательностях. В связи с теоремой 2 возникает следующий более общий вопрос: пусть нам дана заключительно почти периодическая последовательность и оценка сверху на её регулятор почти периодичности. Можно ли только на основании этих данных получить оценку на тот префикс, который достаточно отрезать от этой последовательности, чтобы получить почти периодическую последовательность? Мы доказываем, что такой оценки не существует. Другие теоремы главы 4 являются дальнейшими примерами результатов, в которых доказывается невозможность по обобщённо почти периодической, заключительно почти периодической или почти периодической последовательности и её регулятору почти периодичности найти некоторую характеристику или проверить некоторое свойство. Наиболее общий результат утверждает, что для любого счётного множества М последовательностей, содержащего все периодические последовательности, по обобщённо почти периодической последовательности и её регулятору невозможно определить, принадлежит ли эта последовательность множеству М. В качестве следствий из этих результатов доказывается, что некоторые множества последовательностей не являются регулярными.

В главе 5 исследуются свойства морфических последовательностей. Основной обсуждаемый вопрос — разрешимость проблемы распознавания почти периодичности для морфических последовательностей. Вопрос по-прежнему остаётся открытым, но мы получаем следующие два более слабых результата об эффективной разрешимости почти периодичности для морфических последовательностей специального вида.

Теорема 4. Существует полиномиальный по времени алгоритм, определяющий по чисто морфической последовательности, является ли она почти периодической.

Теорема 5. Существует полиномиальный по времени алгоритм, определяющий по автоматной последовательности, является ли она по-

чти периодической.

Перед доказательством этих результатов мы получаем критерии почти периодичности для чисто морфических и .автоматных последовательностей.

В заключительном разделе 5.4 главы 5 мы получаем следующий результат.

Теорема 6. Подсловнал сложность почти периодических морфических последовательностей не более чем линейна.

Глава 6 посвящена мере апериодичности бесконечных последовательностей.

Расстояние Безиковича определяется как (1в{х, у) = Ит1п£п.^00 : О < г < п — 1,х(г) ф у(г)}. Определим меру апериодичности АМ(х) = т{{с(в(х,£пх) : п ^ 1), где Ь обозначает операцию левого сдвига. Другими словами, АМ(х) — это максимальное такое число от 0 до 1, что можно утверждать, что у последовательности х с любым её собственным сдвигом хотя бы доля АМ(х) символов различны.

Мы приводим результаты работы [6], которые получены автором диссертации. А именно, мы получаем общие верхнюю и нижнюю оценки для меры апериодичности последовательностей для алфавита фиксированного размера. Мы доказываем, что мера апериодичности последовательностей Штурма (ещё одно простейшее обобщение периодических последовательностей) равна 0. После этого мы доказываем, что мера апериодичности последовательности ТУэ — Морса равна 1/3, а также получаем верхнюю оценку на меру апериодичности одного естественного обобщения последовательности Туэ — Морса — последовательностей Пруэ.

Благодарности

Автор выражает глубокую благодарность своему научному руководителю чл.-корр. РАН, проф. Алексею Львовичу Семёнову за постановку задач, поддержку и постоянное внимание к работе, а также к. ф.-м. н. Андрею Альбертовичу Мучнику (1958 — 2007) за постановку задач, многочисленные обсуждения результатов настоящей работы.

Автор благодарен всем сотрудникам кафедры математической логики и теории алгоритмов за прекрасную доброжелательную атмосферу.

Публикации автора по теме диссертации

[1] Притыкин Ю. JI. Конечно-автоматные преобразования строго почти периодических последовательностей // Математические заметки., 80(5):751-756, 2006.

[2] Притыкин Ю. Л. Конечно-автоматные преобразования почти периодических последовательностей и алгоритмическая неразрешимость // Труды XXVIII Конференции молодых учёных, сс. 177-181, мех.-мат. ф-т МГУ им. М. В. Ломоносова, 2006.

[3] Притыкин Ю. Л. О нерегулярности некоторых множеств бесконечных слов // Труды SO-й конференции молодых учёных Информационные Технологии и Системы (ИТиС 2007), сс. 134-137, Институт проблем передачи информации РАН, Москва, 2007.

[4] Pritykin Yu. On almost periodicity criteria for morphic sequences in some particular cases // Proceedings of the 11th International Conference on Developments in Language Theory (DLT 2007), Turku, Finland, Lecture Notes in Computer Science, vol. 4588, pp. 361-370, SpringerVerlag, 2007.

[5] Pritykin Yu. Information in infinite words // Proceedings of the 6th International Conference on Words (Words 2007), Marseille, France, pp. 254-261. Institute de Mathématiques de Luminy, Marseille, France, 2007.

[6] Pritykin Yu., Ulyashkina J. Aperiodicity measure for infinite sequences // Proceedings of the 4th International Computer Science Symposium in Russia (CSR 2009), Novosibirsk, Russia, Lecture Notes in Computer Science, vol. 5675, pp. 274-285. Springer-Verlag, 2009.

В этой работе Притыкину Ю. Л. принадлежит общая идея систематического изучения свойств понятия меры апериодичности, а также результаты теорем 1 — 5. Уляшкиной Ю. С. принадлежит результат теоремы 6.

Подписано в печать зш.ав Формат 60x90 1/16. Усл. печ. л. Ю Тираж /00 экз. Заказ

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета МГУ имени М.В.Ломоносова

1. Введение

1.1. Актуальность темы и цель работы.

1.2. Основные результаты.

2. Обзор основных понятий

2.1. Основные определения

2.2. Морфизмы.

2.3. Основные классы последовательностей.

2.4. Последовательность Туэ — Морса и последовательности Штурма.

2.5. Блочное произведение и его обобщения.

2.6. Конечные автоматы и конечно-автоматные преобразователи

2.7. Произведение с периодической последовательностью

3. Конечно-автоматные преобразования

3.1. Конечно-автоматные преобразования последовательностей со свойствами типа почти периодичности.

3.2. Конечно-автоматные преобразования рекуррентных последовательностей

3.3. Почти обратимые конечно-автоматные преобразования обобщённо почти периодических последовательностей

3.4. Стековые конечно-автоматные преобразования.

4. Вычислимые операторы на бесконечных последовательностях • 56 4.1. Неразрешимость некоторых свойств почти периодических последовательностей.

4.2. Нерегулярность некоторых множеств последовательностей

5. Свойства автоматных и морфических последовательностей

5.1. Разрешимость почти периодичности для морфических последовательностей: предварительные результаты.

5.2. Разрешимость почти периодичности для чисто морфических последовательностей

5.3. Разрешимость почти периодичности для автоматных последовательностей

5.4. Линейность подсловной сложности почти периодических морфических последовательностей.

6. Мера апериодичности бесконечных последовательностей

6.1. Определения и простейшие оценки.

6.2. Мера апериодичности конкретных последовательностей

1.1. Актуальность темы и цель работы

В работе мы рассматриваем разного типа обобщения понятия бесконечной периодической последовательности и исследуем их свойства.

Центральное понятие работы — почти периодические последовательности. Последовательность символов конечного алфавита почти периодическая, если для каждого конечного подслова и последовательности найдётся такое натуральное число п, что в каждом подслове длины п последовательности найдётся вхождение слова и.

Впервые почти периодические последовательности были рассмотрены в связи с символической динамикой. Продолжая и ссылаясь на работы Адамара и Пуанкаре, Морс в 1921 году опубликовал работу [24], в которой среди прочего определил почти периодические последовательности (он называл их рекуррентными). В 1938 — 1940 годах вышли работы Морса и Хедлунда "Символическая динамика" [22, 23], в которых многие свойства почти периодических последовательностей были подробно исследованы.

Идея символической динамики заключается в сопоставлении траектории в непрерывной динамической системе последовательности букв конечного алфавита. Понимая траекторию как движение точки в некотором пространстве, мы, во-первых, выделяем в пространстве конечное количество областей и, во-вторых, выбираем дискретное множество моментов времени (например, через каждую фиксированную единицу времени), после чего смотрим, в каких областях оказывается точка в эти моменты. Траектории точки сопоставляется бесконечная последовательность букв конечного алфавита, где буквы соответствуют областям пространства.

Более формально, топологическая динамическая система — это топологическое пространство V с заданным на нём непрерывным отображением f:V—^V. Рассмотрим V, / — топологическую динамическую систему, Ai, ., Ak — попарно непересекающиеся открытые подмножества в V, и р — точку, орбита которой {fn(p) : п £ N} лежит в |jf=i-A-k' Определим последовательность х: N —> условием fn{p) £ Ах(пу Таким образом, (некоторым) точкам пространства V мы сопоставили последовательности букв алфавита А = {1,., к}. При этом применению отображения / соответствует операция левого сдвига L: £(аоСца2аз .) = а\а2аъ • •

Ясно, что периодические последовательности описывают только самые простые ситуации. Однако оказывается, что в довольно широком классе ситуаций возникающая символическая последовательность будет близка к периодической. Это наблюдение можно формализовывать разными способами. Вот один из них. Результат этой теоремы, видимо, уже является фольклором. Доказательство можно найти в [25].

Теорема 1.1 ([25]). Если пространство V компактно, и орбита каждой точки плотна в V, то последовательность х почти периодическая:

Более того, несложно показать, что каждая почти периодическая последовательность может быть получена таким образом, как описано в теореме 1.1. Для этого надо взять пространство всех последовательностей с топологией, порождённой метрикой dc, для каждой буквы а в качестве области Аа взять множество последовательностей, начинающихся с а, и в качестве отображения / взять отображение L левого сдвига, а в качестве V взять замыкание х относительно действия /, после чего замкнуть получившееся множество относительно метрики dc- Подробнее см., например, [20].

Топологическая динамическая система, удовлетворяющая свойству из условия теоремы 1.1, называется минимальной. Почти периодические последовательности также называют минимальными последовательностями. Они обладают следующим свойством минимальности. Обозначим через Fac(a?) множество всех конечных подслов последовательности х. Почти периодические последовательности обладают минимальным множеством подслов среди всех последовательностей, в следующем смысле: для любых бесконечных последовательностей х и у если х почти периодическая и Fac(?/) С Fac(rc), то Fac(?/) = Fac(aj), и для любой последовательности у существует почти периодическая последовательность ж, такая что Fac(x) С Fac(?/) (см. предложение 2.1).

Это утверждение — пример комбинаторного свойства почти периодических последовательностей. Комбинаторные результаты появляются уже в [22, 23]. Кроме того, конечные и бесконечные слова и до этого изучались с комбинаторной точки зрения. Зарождением соответствующей области — комбинаторики слов — принято считать работы Туэ [34, 33], в которых он, в частности, изучает свойства последовательности, теперь называемой последовательность Туэ — Морса (см. 2.4), и доказывает её бескубность (подробнее о работах Туэ см. в [6]). Отметим, что Туэ не имел в виду каких-то конкретных применений своих результатов и считал рассматриваемые им вопросы представляющими самостоятельный интерес (см. [2]). Сейчас комбинаторика слов — активная область, и в настоящей работе к ней можно отнести многие результаты.

Впервые рассмотренные в символической динамике, почти периодические последовательности нашли применение и в математической логике.

Рассмотрим следующие вопросы о последовательности х: входит ли в х символ а? Входит ли слово и? Входит ли слово и бесконечно много раз? Можно сформулировать и более сложные вопросы про последовательность. Когда на такие вопросы можно отвечать алгоритмически, получая на вход последовательность?

Различные, в том числе и перечисленные только что, свойства бесконечных последовательностей могут быть выражены в логической теории первого порядка. Под такой теорией для последовательности х £ мы будем понимать следующее. Формально, в качестве структуры возьмём (N, S, <, X), где N — множество натуральных чисел, которое пробегают индивидные переменные, S — двухместный предикат следования, < — двухместный предикат порядка на натуральных числах, X — функциональный символ, интерпретируемый как последовательность х: N —> А. В качестве теории берём обычную теорию первого порядка, несущественным образом расширенную атомарными формулами вида Х(п) — а для п £ N и а £ А] истинность формул интерпретируем естественным образом. Во всех рассматриваемых нами теориях мы подразумеваем наличие двухместного предиката равенства, интерпретируемого естественным образом.

Ясно, что у такой реализации есть много вариантов, эквивалентных между собой по выразительным способностям. Например, можно было вместо двухместного предиката следования взять в структуру одноместную функцию следования. Можно было и не брать предикат следования вообще, потому что он выразим через неравенство. Точно так же вместо одной функции X можно было взять семейство предикатов Ха по одному для каждого а 6 А, истинных ровно там, где в х стоит буква а. Можно обойтись и меньшим — логарифмическим по отношению к размеру алфавита последовательности — количеством предикатов. Кроме того, поскольку константа 0 выразима в определённой выше структуре, ясно, что можно было, не меняя множество выразимых формул, добавить в структуру все константы. Поэтому можно переходить от одной конкретной реализации к другой, если понадобится.

Теорию, определённую выше, будем обозначать T(N, <,#).

Несложно видеть, что простые свойства последовательности х, типа упомянутых в начале раздела, можно выразить в теории T(N, <, х). Например, формула Vp3g3r q > р Л S(q, г) Л X(q) = О Л X(r) = 1 означает свойство вхождения в х бесконечное количество раз слова 01. Тем не менее, некоторые свойства, которые, вероятно, хотелось бы выразить, в теории первого порядка выразить нельзя, например, "последовательность в алфавите {а, &}, в которой между любыми последовательными вхождениями Ъ (такими, между которыми нет других вхождений 6) входит нечётное количество букв а".

Гораздо больше можно выразить в более сильной монадической теории второго порядка. В такой теории, кроме обычных переменных по натуральным числам p,q,., разрешены также монадические переменные по множествам (или по одноместным предикатам) P,Q,----Вводятся также соответствующие атомарные формулы вида -Р(р), Q{p), • • •, обозначающие "р принадлежит Р", "р принадлежит Q". Разрешены также кванторы по монадическим переменным. Такую теорию мы будем обозначать MT(N, <, х).

Теории, аналогичные вышеперечисленным, но не расширенные последовательностью, будем обозначать соответственно T(N, <), MT(N, <).

Теория MT(N, <,ж) богаче теории T(N, <,х). Например, упомянутое выше не выразимое в теории первого порядка свойство в монадическои теории можно выразить так: Л X(q) Л р < q Л \/r(p < г Л г < q -iX(r)) 3Y(VuV?;(S(u, v) (Y(u) Y(v))) Л Y(p) Л Y(g))).

Как и в случае с теориями первого порядка, в описанной формализации монадической теории многое можно реализовать по-другому. Например, можно отказаться от неравенства, потому что в монадической теории оно выразимо через следование. Как и в случае теорий первого порядка, здесь можно переходить от одной реализации к другой для удобства.

Для формулы ф в любой из вышеописанных теорий будем обозначать через Ь(ф) множество всех последовательностей х, для которых эта формула верна (то есть верна, если интерпретировать входящую в неё единственную свободную переменную по функциям X как х).

Естественным вопросом о любой теории является вопрос о её разрешимости. Теория разрешима, если существует алгоритм, который по любой замкнутой формуле определяет её истинность. Оказывается, что благодаря применению теории автоматов для достаточно широких классов последовательностей можно получить критерий разрешимости их монадических теорий.

Интересным образом оказывается, что свойства типа почти периодичности полезны и, более того, естественно возникают при решении такого типа задач. Следующее понятие было введено Семёновым в [37]. Назовём последовательность обобщённо почти периодической, если каждое конечное слово либо входит в неё бесконечное количество раз с ограниченными интервалами между соседними вхождениями, либо входит лишь конечное количество раз. Заметим, что естественное предположение о том, что такие последовательности исчерпываются почти периодическими последовательностями с приписанным к ним префиксом, оказывается неверным, см. предложение 2.4. Обобщённо почти периодическая последовательность эффективно обобщённо почти периодическая, если по каждому слову можно определить, входит ли оно в последовательность бесконечное или конечное количество раз, и в первом случае можно также определить оценку сверху на расстояние между соседними вхождениями, а во втором можно также определить оценку на длину префикса, которым ограничиваются вхождения.

Следующий результат теоремы 1.2 о теориях первого порядка был получен в [37].

Теорию T'(N, <, х) (незначительную модификацию теории T(N, <, х)) определим следующим образом. Пусть Р — система предикатов, задающая последовательность х. Термами теории будут выражения вида с, х + с, где — переменная. Атомарными формулами теории будут выражения г < г', г > г', р(т), где р — предикат из системы Р, т и т' — термы. Несмотря на то, что значения термов могут не лежать в N, отношения, задаваемые атомарными формулами, всюду определены на N.

Мы говорим, что теория бескванторная, если для каждой формулы теории найдётся эквивалентная ей бескванторная.

Теорема 1.2 ([37]). 1) Если теория T'(N, <,х) бескванторная, то х е GAP.

2) Пусть х G GAP. Тогда теория T'(N, <, х) бескванторная, причём она разрешима, если и только если х эффективно обобщённо почти периодична.

Вопрос о разрешимости монадических теорий оказывается более сложным. В [8] была доказана разрешимость теории MT(N, <), при помощи сопоставления формул теории конечным автоматам на бесконечных последовательностях. Конечный автомат Бюхи состоит из конечного множества состояний, некоторые из которых называются принимающими, а какое-то одно — начальным, а также правила перехода, по которому из любого состояния, получив на вход букву алфавита, определяется следующее состояние. Если правило по букве и текущему состоянию определяет следующее состояние однозначно, автомат называется детерминированным, в противном случае — недетерминированным. По умолчанию мы считаем автомат Бюхи недетерминированным. Рассмотрим автомат Бюхи, которому на вход подаётся бесконечная последовательность. Автомат изначально находится в своём начальном состоянии и далее, читая буквы последовательности по одной, меняет состояние на одно из разрешённых в соответствии с правилом перехода. Получившаяся последовательность состояний называется ходом вычисления автомата на последовательности. Поскольку автомат недетерминированный, ходов может быть бесконечно много. Мы говорим, что автомат

Бюхи принимает последовательность, если, будучи запущенным на последовательности, он может побывать в одном из своих заключительных состояний бесконечно много раз, то есть существует ход, в котором одно из заключительных состояний встречается бесконечно много раз. Для автомата Бюхи М множество всех последовательностей, которые принимаются автоматом М, обозначим L(M).

Теорема 1.3 ([8]). Существует алгоритм, который по каждому автомату Бюхи М строит формулу ф монадического языка, такую что L(M) = Ь(ф), и наоборот, по любой формуле ф строит такой автомат Бюхи М, что Ь(ф) = L{M).

Следствие 1.4 ([8]). Теория MT(N, <) разрешима.

После этого возникает естественный вопрос о разрешимости теорий вида MT(N, <,ж), то есть MT(N, <), расширенной некоторой последовательностью х. Несложно видеть, что выполняется следующее важное для нас следствие из теоремы 1.3.

Следствие 1.5 ([8]). Монадическая теория последовательности х разрешима тогда и только тогда, когда существует алгоритм, который по любому автомату Бюхи может определить, принимает ли этот автомат последовательность х или нет.

Конечно, теория MT(N, <,ж) разрешима, если последовательность х выразима в исходной теории, но запас таких последовательностей невелик — это периодические последовательности, возможно, с предперио-дом. Оказывается, что можно получить критерий разрешимости теории MT(N, <, х), если ограничиться рассмотрением обобщённо почти периодических последовательностей.

Пусть последовательность х обобщённо почти периодическая. Регулятором почти периодичности последовательности х называется такая функция Rx: N —> N, которая на числе п равна минимальному такому Z, что всякое слово длины п, входящее в ж, может входить только в начальный отрезок х длины I и не может входить далее, а также каждое слово длины п, входящее в х бесконечно много раз, входит в каждый отрезок длины I. Назовём последовательность эффективно обобщённо почти периодической, если она является вычислимой обобщённо почти периодическои последовательностью, и некоторая оценка сверху на регулятор почти периодичности такой последовательности вычислима. Другими словами, вычислимая обобщённо почти периодическая последовательность х эффективно обобщённо почти периодична, если можно эффективно по п оценивать префикс, которым ограничиваются все вхождения слов длины п, входящих в х конечное количество раз, и эффективно оценивать максимальное расстояние между вхождениями слов длины п, входящих бесконечное количество раз. Следующий критерий был получен в [38].

Теорема 1.6 ([38]). Теория MT(N, <,х) обобщённо почти периодической последовательности х разрешима тогда и только тогда, когда х эффективно обобщённо почти периодична.

Для доказательства этой теоремы необходимо разобраться в том, как ведёт себя конечный автомат, запущенный на обобщённо почти периодической последовательности. Этот вопрос связан со следующей серией вопросов — понять, как меняются или насколько сохраняются различные свойства последовательностей при применении к ним различного вида преобразований. Например, несложно видеть, что если стереть каждый второй символ почти периодической последовательности, то полученная последовательность будет также почти периодической. Другой пример — если закодировать каждый блок длины 10 почти периодической последовательности символом некоторого нового алфавита, причём использовать разные символы для разных блоков и одинаковые символы для одинаковых блоков, то полученная последовательность в новом алфавите будет снова почти периодической. Аналогичные свойства выполнены и для обобщённо почти периодических последовательностей. Рассмотрим менее тривиальный пример: если рассмотреть покомпонентное произведение почти периодической последовательности с периодической последовательностью, то можно доказать, что результат будет снова почти периодическим. Противоположный пример — рассмотрим операцию приписывания к последовательности символа 0. Ясно, что обобщённо почти периодические последовательности сохраняются под действием такого преобразования, но почти периодические нет — 1111. .почти периодична, но 01111. нет.

Можно рассматривать и гораздо более сложные преобразования, задаваемые алгоритмами разной степени сложности устройства. Простейшие алгоритмические преобразования — конечно-автоматные, объединяющие в себе вышеперечисленные и многие другие простейшие преобразования над последовательностями. Конечно-автоматный преобразователь состоит из конечного множества состояний, одно из которых выделено и называется начальным, и правила перехода, в соответствии с которым, получив на вход символ некоторого алфавита А, преобразователь определяет следующее состояние, а также выходное слово в некотором алфавите В (это слово может иметь произвольную длину, в том числе и нулевую). Конечно-автоматный преобразователь, будучи запущенным на бесконечной последовательности, изначально находится в начальном состоянии, и получая по одному символы входной последовательности, в соответствии с правилом перехода меняет состояние и печатает слово на выходной ленте. Напечатанное в итоге на ленте бесконечное слово есть результат конечно-автоматного преобразования исходной последовательности. Основным средством доказательства теоремы 1.6 в [38] стал следующий результат, по существу доказанный в [38]. Доказательство в явном виде можно найти также в [25] или в [43]. См. также теорему 3.1.

Теорема 1.7 ([38]). 1) Множество обобщённо почти периодических последовательностей сохраняется под действием конечно-автоматных преобразований.

2) Множество эффективно обобщённо почти периодических последовательностей сохраняется под действием конечно-автоматных преобразований.

Из теоремы 1.7 следует теорема 1.6. Однако результат теоремы 1.7 представляет и самостоятельный интерес. Известны и другие результаты о сохранении классов последовательностей под действием конечно-автоматных преобразований. В частности, в [9] доказано, что класс автоматных последовательностей, определяемый ниже, сохраняется под действием равномерных конечно-автоматных преобразований (см. также [4]). Под равномерными мы понимаем такие конечно-автоматные преобразования, которые, получив на вход букву, всегда выдают на выход ровно одну букву. Как доказано в [10], морфические последовательности см. ниже) сохраняются под действием конечно-автоматных преобразований (см. также [4]).

Таким образом, представляется естественным более детально изучить свойства замкнутости классов последовательностей с различными свойствами типа почти периодичности относительно конечно-автоматных преобразований.

Другие важные для нас классы последовательностей, обладающих свойствами, близкими к свойствам периодических последовательностей, являются автоматные и морфические последовательности.

Любая периодическая последовательность (возможно, с предперио-дом), например, 3142857142857142. (цифры десятичной записи числа 22/7) может быть порождена машиной с конечной памятью. Достаточно иметь информацию о предпериоде и периоде последовательности: в нашем случае 3 и 142857. И наоборот, любая машина с конечной памятью, печатающая символы конечного алфавита, порождает заключительно периодическую последовательность. Действительно, во время её работы в какой-то момент конфигурация машины полностью совпадёт с какой-то из уже встречавшихся, и так начнётся период в выходной последовательности.

Если разрешить машине обращаться к символам, написанным ранее, класс порождаемых последовательностей существенно возрастёт. При некоторых ограничениях на порядок, в котором ранее написанные символы читаются снова, мы получим класс автоматных последовательностей, введённый Кобхэмом в [9].

Например, последовательность Туэ — Морса (см. раздел 2.4) t = 0110100110010110. удовлетворяет такому условию: если на n-м месте стоит 0, то на 2гг-м и (2п + 1)-м будет 0 и 1 соответственно, а если на п-м месте 1, то, наоборот, на 2п-м и (2п + 1)-м будет 1 и 0 соответственно.

Кобхэм вводит иерархию на автоматных последовательностях, в зависимости от того, как далеко надо заглядывать назад, чтобы написать очередной символ. В ^-автоматных последовательностях п-й символ определяет, что стоит на местах кп, кп 1, кп + 2,., (к + 1 )п — 1.

Формально определим автоматные последовательности двумя эквива-' лентными способами.

Рассмотрим конечный автомат, действующий на словах в алфавите {0,1,., к — 1}. Каждому состоянию автомата соответствует буква в некотором другом алфавите А (разным состояниям могут соответствовать одинаковые буквы). Автомат действует так: получает на вход слово в алфавите Е&, производит вычисления и выдаёт ту букву алфавита А, которая соответствует последнему состоянию в вычислении. Последовательность х букв алфавита А называется к-автоматной, если существует конечный автомат вышеуказанного вида, который, будучи запущенным на числе п, записанном в &-ичной системе счисления, выдаёт букву х{тъ). Когда ясно или неважно, о каком к идёт речь, приставку мы будем опускать.

Теперь опишем другой подход. Пусть А, В — конечные алфавиты. Рассмотрим операцию подстановки, которая каждую букву алфавита А отображает в слово алфавита В. Результатом применения подстановки к конечному слову или бесконечной последовательности в алфавите А будет конкатенация образов букв, составляющих это слово или последовательность. Такие отображения подстановки будем называть морфиз-мами. Морфизм называется ^-равномерным, если длины образов всех букв совпадают и равны к.

Ограничимся теперь рассмотрением ситуации, когда алфавиты А и В совпадают. Нас интересуют бесконечные последовательности, являющиеся неподвижными точками морфизмов, причём неподвижными точками достаточно общего вида. Пусть ф — морфизм в алфавите А, и s — буква алфавита А, такая что слово 0(s) начинается с s. Будем итерировать ф на s, получим слова s, </>(s), 02(s), </>3(s), ф4(э), ., каждое из которых начинается с предыдущего. Если длина слова 0n(s) стремится к бесконечности с ростом п, можно корректно определить бесконечную последовательность </>°°(s), началами которой являются слова 0n(s) для любого п. Последовательности х = <^°°(s), которые можно получить таким способом, называются чисто морфическими. Несложно видеть, что чисто морфическая последовательность, порождённая морфизмом ф, является неподвижной точкой под действием этого морфизма. Последовательности, получающиеся из чисто морфических отождествлением некоторых символов, называются морфическими. Как доказал Кобхэм в [9], fc-автоматные последовательности — это в точности морфические последовательности, полученные из порождённых ^-равномерными мор-физмами чисто морфических последовательностей.

Морфические последовательности, точнее, тесно связанные с ними

DOL-последовательности и, более общо, L-системы (системы Линден-майера), впервые появились в работах математика и биолога Линден-майера для описания процессов развития живых организмов (например, см. сборник [30]). Однако впоследствии морфические последовательности стали рассматриваться и в теории динамических систем, комбинаторике слов, информатике (см. [4, 16, 29, 30]). Автоматные последовательности неявно были впервые рассмотрены в [7], впервые систематически изучались в [9]. Хорошей монографией, посвящённой автоматным и морфиче-ским последовательностям, является [4].

Множества морфических и почти периодических последовательностей находятся в общем положении. Действительно, существуют последовательности, являющиеся морфическими, но не почти периодическими: например, последовательность в алфавите {0,1}, у которой каждый символ с номером 2" равен 1, а все остальные равны 0 (мы нумеруем последовательности, начиная с 0), 2-автоматна (легко построить автомат, который будет распознавать числа вида 1000. 00 в двоичной системе счисления), но не является периодической. Существуют почти периодические, но не морфические последовательности; более того, почти периодических последовательностей континуум (как доказано, например, в [17]), а морфических лишь счётное число. Существуют также и одновременно морфические и почти периодические последовательности. Конечно, все периодические последовательности являются таковыми. Среди непериодических такова, например, последовательность Туэ — Морса, упомянутая выше (см. также раздел 2.4). Заметим также, что морфические последовательности можно конечно описать — для этого нужно описать алфавит, морфизм, букву, на которой итерируется морфизм, и последующий способ отождествления букв в чисто морфической последовательности. Поэтому можно ставить алгоритмические вопросы о морфических последовательностях. Довольно естественным является вопрос о существовании алгоритма для следующей проблемы.

Проблема распознавания почти периодичности морфических последовательностей (ППМ).

Дано: конечное описание морфической последовательности.

Определить: является ли эта последовательность почти периодической.

Многие алгоритмические задачи, связанные с морфизмами, являются довольно сложными и интересными. Хорошим обзором по таким задачам является [16]. Один из самых известных примеров такой задачи — проблема соответствий Поста (Post correspondence problem), которая неразрешима (см. [32], а также [16]). Про проблему ППМ до сих пор неизвестно, является ли она разрешимой, хотя гипотеза о разрешимости является довольно правдоподобной. В настоящей работе мы исследуем некоторые частные случаи проблемы ППМ, возникающие при ограничении множества входов на морфические последовательности специального вида.

Тесто связанный с проблемой ППМ вопрос или даже вариант формулировки — получение по возможности как можно более компактного и эффективно проверяемого критерия почти периодичности для морфи-ческих последовательностей. Вопрос о получении такого критерия для чисто морфических последовательностей был поставлен как открытый в [4], раздел 10.12, проблема 5.

Следующая тема диссертации — подсловная сложность, одна из простейших и наиболее естественных характеристик бесконечных последовательностей. Подсловной сложностью последовательности х называется такая функция Р: N —Y N, что р(п) равно количеству слов длины п, входящих в последовательность х. Для последовательностей в алфавите из т символов подсловная сложность может варьироваться от 1 до тп. Как доказано в [22] (также см. предложение 2.5), подсловная сложность последовательности ограничена тогда и только тогда, когда последовательность является заключительно периодической.

Асимптотическое поведение подсловной сложности последовательностей широко изучалось, например, см. обзоры [5, 14]. В серии работ, завершающейся работой [26], доказано, что подсловная сложность чисто морфической последовательности может удовлетворять одной из следующих пяти асимптотик: 0(1), ©(n), ©(nloglogn), ©(nlogn), ©(п2). В [27] показано, что существуют примеры морфических последовательностей с подсловной сложностью вида @(п1+*) для каждого натурального к ^ 1. После этого про подсловную сложность морфических последовательностей произвольного вида долгое время было ничего неизвестно. Наконец, в [11] было доказано, что подсловная сложность морфической последовательности имеет один из следующих видов: О (nlogn) или ©(п1+*) для некоторого к Е N. Таким образом, для полного описания возможных асимптотик подсловной сложности морфической последовательности осталось разобраться подробнее со случаем 0{n\ogn).

В случае автоматных последовательностей ситуация существенно проще. Как доказано в [9], подсловная сложность автоматной последовательности не более чем линейна.

Несложно показать (например, см. [14]), что подсловная сложность почти периодической последовательности в алфавите из т символов не может быть больше тап для некоторого фиксированного а < 1. При этом можно показать, что для любого /3 < 1 существует почти периодическая последовательность в алфавите из т символов с подсловной сложностью не меньше тРп (например, см. [46]).

Оказывается, подсловная сложность последовательности, являющейся одновременно морфической и почти периодической, устроена гораздо проще. Как мы доказываем в настоящей работе, подсловная сложность таких последовательностей не более чем линейна. Отметим, что линейность подсловной сложности почти периодических чисто морфических последовательностей была известна ранее (например, см. [29]).

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

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

1. Devyatov R. On subword complexity of morphic sequences // Proceedings of the 3rd International Computer Science Symposium in Russia (CSR 2008), Moscow, Russia, Lecture Notes in Computer Science, vol. 5010, pp. 146-157. Springer-Verlag, 2008.

2. Ehrenfeucht A., Rozenberg G. Repetition of subwords in DOL languages // Information and Control, 59(1-3): 13-35, 1983.

3. Ferenczi S. Complexity of sequences and dynamical systems // Discrete Mathematics, 206(1): 145-154, 1999.

4. Grant E., Shallit J., Stoll T. Bounds for the discrete correlation of infinite sequences on к symbols and generalized Rudin-Shapiro sequences // Preprint arXiv:0812.3186, 2008.

5. Harju Т., Karhumaki J. Morphisms // In G. Rozenberg, A. Salomaa, editors, Handbook of formal languages, vol. 1, pp. 439-510. Springer-Verlag, 1997.

6. Keane М. Generalized morse sequences // Z. Wahrscheinlichkeitstheorie verw. Geb., 10:335-353, 1968.

7. Lothaire M. Combinatorics on Words // Cambridge University Press, 2nd edition, 1997.

8. Lothaire M. Algebraic Combinatorics on Words // Cambridge University Press, 2002.

9. McNaughton R. Testing and generating infinite sequences by a finite automaton // Information and Control, 9:521-530, 1966.

10. Morse M., Hedlund G. A. Symbolic dynamics // American Journal of Mathematics, 60(4):815-866, 1938.

11. Morse M., Hedlund G. A. Symbolic dynamics ii: Sturmian trajectories // American Journal of Mathematics, 62(l):l-42, 1940.

12. Morse M. Recurrent geodesies on a surface of negative curvature // Transactions of the American Mathematical Society, 22:84-100, 1921.

13. Muchnik An., Semenov A., Ushakov M. Almost periodic sequences // Theoretical Computer Science, 304(1-3): 1-33, 2003.

14. Pansiot J.-J. Subword complexities and iteration // Bulletin of the European Association for Theoretical Computer Science, 26:55-62, 1985.

15. Prouhet M. E. Memoire sur quelques relations entre les puissances des nombres. Comptes Rendus des Seances de I'Academie des Sciences, 33:225, 1851. Available ' at http://gallica.bnf.fr/ark:/12148/bpt6k29901.image.f227.langFR

16. Queffelec M. Substitution Dynamical Systems—Spectral Analysis // Lecture Notes in Mathematics, vol. 1284. Springer-Verlag, 1987.

17. Rozenberg G., Salomaa A., editors. Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology // Springer-Verlag, 1992.

18. Seebold P. On some generalizations of the Thue-Morse morphism. Theoretical Computer Science, 292:283-298, 2003.

19. Sipser M. Introduction to the Theory of Computation // PWS Publishing Company: Boston, 2nd edition, 2005.

20. Thue A. Uber die gegenseitige Lage gleicher Teile gewisser Zeichenrei-hen // Selected mathematical papers of Axel Thue, pp. 413-478. Oslo, Norway: Universitetsforlaget, 1977.

21. Thue A. Uber unendliche Zeichenreihen // Selected mathematical papers of Axel Thue, pp. 139-158. Oslo, Norway: Universitetsforlaget, 1977.

22. Каток А. Б., Хасселблат Б. Введение в современную теорию динамических систем // Факториал, 1999. Пер. с англ.: Katok A., Has-selblatt В. Introduction to the Modern Theory of Dynamical Systems // Cambridge University Press, 1995.

23. Роджерс X. Теория рекурсивных функций и эффективная вычислимость // Мир, 1972. Пер. с англ.: Rogers Н., Theory of Recursive Functions and Effective Computability // MIT Press, 1967.

24. Семёнов A. JI. О некоторых расширениях арифметики сложения натуральных чисел // Известия АН СССР, серия математическая, 43(5):1175—1195, 1979.

25. Семёнов A. JI. Логические теории одноместных функций на натуральном ряде // Известия АН СССР, серия математическая, 47(3):623-658, 1983.Работы автора по теме диссертации

26. Притыкин Ю. JI. Конечно-автоматные преобразования строго почти периодических последовательностей // Математические заметки, 80(5):751-756, 2006.

27. Притыкин Ю. JI. Почти периодичность, конечно-автоматные преобразования и вопросы эффективности // Известия ВУЗ. Математика, в печати. См. препринт arXiv:cs/0607009.

28. Притыкин Ю. JI. Конечно-автоматные преобразования почти периодических последовательностей и алгоритмическая неразрешимость // Труды XXVIII Конференции молодых учёных, сс. 177-181, мех.-мат. ф-т МГУ им. Ломоносова, 2006.

29. Притыкин Ю. JI. О нерегулярности некоторых множеств бесконечных слов /./ Труды 30-й конференции молодых учёных Информационные Технологии и Системы (ИТиС 2007), сс. 134-137, Институт проблем передачи информации РАН, Москва, 2007.

30. Мучник Ан. А., Притыкин Ю. JL, Семёнов A. JI. Последовательности, близкие к периодическим // Препринт arXiv:0903.5316, 2009.

31. Pritykin Yu. Information in infinite words // Proceedings of the 6th International Conference on Words (Words 2007), Marseille, France, pp. 254261. Institute de Mathematiques de Luminy, Marseille, France, 2007.

32. Nicolas F., Pritykin Yu. On uniformly recurrent morphic sequences // International Journal of Foundations of Computer Science, to appear.