О комбинаторных свойствах бесконечных слов, порожденных итерациями морфизмов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

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

1.1. Формальные языки и D0L слова.

1.2. Виды морфизмов.

1.3. Циркулярность.

1.4. Функции от бесконечных слов.

2. Критерий циркулярности равноблочных буферных DOL слов

2.1. Формулировка критерия.

2.2. Доказательство критерия

2.3. Множество слов без точек синхронизации.

2.4. Проверка критерия.

2.5. Случай бинарного алфавита.

3. Свойства равноблочных буферных DOL слов

3.1. Соотношение на допустимые слова.

3.2. Комбинаторная сложность.

3.3. Частоты слов.

3.4. Функция рекуррентности и родственные ей

4. Комбинаторная сложность бипрефиксных DOL слов 77 4.1. Сложность и биспециальные слова.

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

Пусть дан конечный алфавит £ и морфизм <р : £* —> £*, то есть отображение, для любых слов ху над Е удовлетворяющее равенству ср(ху) = (f{x)(f{y). Пусть образ <р{а) некоторого символа а алфавита £ начинается с а. Тогда, как нетрудно видеть, существует конечное или бесконечное слово w, начинающееся с а и удовлетворяющее равенству w = tp{w).

Слово w называется неподвижной точкой морфизма у? или D0L словом.

D0L слова представляют собой один из простейших по способу задания классов бесконечных непериодических последовательностей. Введенные первоначально в 1968 году для моделирования развития живых организмов [6], впоследствии они нашли применение во многих областях математики и теоретической кибернетики. Причиной этому послужили, с одной стороны, близость механизма их порождения к теории автоматов, а с другой — их фракталоподобная структура, привлекающая внимание специалистов в теории динамических систем [64].

В настоящее время D0L слова активно используются в случаях, когда требуется построить пример бесконечного слова с заданными свойствами. Первым из таких примеров стало построенное еще А. Туэ [67] в начале века бесконечное слово над двухбуквенным алфавитом, избегающее кубов (то есть не содержащее трех последовательных вхождений одного и того же слова), ныне известное как слово Туэ-Морса. В той же работе Туэ было впервые построено слово над трехбуквенным алфавитом, избегающее квадратов (двух последовательных вхождений одного и того же слова). Существование таких бесквадратных слов помогло П. С. Новикову и С. И. Адяну решить проблему Бернсайда для групп [2]. Новым полезным примером D0L слова может служить слово Керянена [52] над четырехбуквенным алфавитом, избегающее двух последовательных вхождений слов, равных по составу, и послужившее окончательным решением стоявшей около 30 лет проблемы Эрдёша [42].

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

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

Перейдем к описанию содержания диссертационной работы по главам.

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

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

Основными результатами главы 2 являются критерий циркулярности неподвижных точек равноблочных буферных морфизмов (теорема 2.1) и вытекающее из него описание структуры множества под-слов нециркулярных D0L слов (предложение 2.5). Приведены также алгоритм проверки критерия и подробное исследование циркулярности равноблочных D0L слов над двухбуквенным алфавитом.

Глава 3 посвящена исследованию свойств неподвижных точек равноблочных буферных морфизмов. С использованием результатов главы 2 получены явные выражения для их комбинаторной сложности как в циркулярном, так и в нециркулярном случае (теорема 3.8); приведены соответствующие примеры, включая формулу для комбинаторной сложности слова Керянена (пример 3.3).

Далее исследуются частоты слов: описывается новый общий алгоритм их вычисления по формуле (3.7), который затем преобразуется в явную формулу для частот подслов равноблочного буферного циркулярного слова в терминах частотных таблиц (теорема 3.15). Приводятся примеры вычисления частот. Заметим, что частоты подслов в нециркулярных D0L словах либо не существуют, либо описываются тривиальным образом, поэтому требование циркулярности не ограничивает общности.

Последней серией результатов главы 3 является описание в тех же терминах функции рекуррентности и родственных ей функций (теорема 3.20); для удобства формулировок они описываются только для равноблочных маркированных циркулярных D0L слов.

Наконец, глава 4 посвящена вычислению комбинаторной сложности неподвижных точек бипрефиксных морфизмов, то есть D0L слов гораздо более широкого класса. Вычисление их комбинаторной сложности опирается на отличную от примененной в главе 3 технике биспециалъных подслов, а формула для комбинаторной сложности (формула (4.5)), оставаясь явной, оказывается более громозкой. В конце главы применимость полученной формулы демонстрируется на примере (раздел 4.4).

1. Августинович С. В. Число различных подслов заданной длины в последовательности Морса-Хедлунда // Сиб. журн. исслед. операций. 1994. Т. 1, № 2. С. 3-7.

2. Адян С. И. Проблема Бернсайда и тождества в группах. М.: Наука, 1975.

3. Белов А. Я., Кондаков Г. В. Обратные задачи симвоолической динамики // Фундаментальная и прикладная математика. 1995. Т. 1, № 1. С. 71-79.

4. Зимин А. И. Блокирующие множества термов // Мат. сб. 1982. Т. 119, вып. 3. С. 363-375.

5. Лаллеман Ж. Полугруппы и комбинаторные приложения. М.: Мир, 1985.

6. Линденмайер А. Биологические аспекты теории развивающихся систем и языков // Кибернетический сб. 1980. Новая серия, вып. 17.

7. Липатов Е. П. Об одной классификации двоичных наборов и свойствах классов однородности // Проблемы кибернетики. 1982. М.: Наука. Т. 39, С. 67-84.

8. Петров А. Н. Последовательность, которая избегает любое полное слово // Мат. заметки. 1988. т. 44, № 4, С. 517-522.

9. Саломаа А. Жемчужины теории формальных языков. М.: Наука, 1986.

10. Фрид А. Э. О комбинаторной сложности итеративно порождаемых символьных последовательностей // Дискрет, анализ и ис-след. операций. Сер. 1. 1997. Т. 4, № 1. С. 53-59.

11. Фрид А. Э. Частота вхождения слов в DOL-последователь-ность // Дискрет, анализ и исслед. операций. Сер. 1. 1998. Т. 5, № 1. С. 82-87.

12. Allouche J.-P. The number of factors in a paperfolding sequence // Bull. Austral. Math. Soc. 1992. V. 46, P. 23-32.

13. Allouche J.-P., Bousquet-Melou M. Canonical positions for the factors in paperfolding sequences // Theoret. Comput. Sci. 1994. V. 129, P. 263-278.

14. Allouche J.-P., Bousquet-Melou M. On the conjectures of Rauzy and Shallit for infinite words // Comment. Math. Univ. Carolinae. 1995. V. 36, P. 705-711.

15. Allouche J.-P., Shallit J. The ubiquitous Thue-Morse sequence // Sequences and their applications. London: Springer, 1999. P. 1-16.

16. Allouche J.-P., Zamboni L. Q. Algebraic irrational binary numbers cannot be fixed points of non-trivial constant length or primitive morphisms // J. of Number Theory. 1998, V. 69, P. 119-124.

17. Arnoux P., Mauduit C. Complexite de suites engendrees par des recurrences unipotentes // IML preprint 95-24, 1995.

18. Arnoux P., Rauzy G. Representation geometrique de suites de complexite 2n + 1 // Bull. Soc. Math. France. 1991. V. 199, P. 199215.

19. Avgustinovich S. V., For-Der-Flaass D. G., Frid A. E. Arithmetical complexity of infinite words // to be published.

20. Baryshnikov Yu. Complexity of trajectories in rectangular billiards // Commun. Math. Phys. 1995, V. 174, P. 43-56.

21. Beal M.-P., Mignosi F., Restivo A. Minimal forbidden words and symbolic dynamics // Theoretical Aspects of Computer Science. Berlin: Springer, 1996. P. 555-566. (Lecture Notes in Comput. Sci.; V. 1046).

22. Bean D. R., Ehrenfeucht A., McNulty G. Avoidable patterns in strings of symbols // Pacific. J. Math. 1979. V. 85, no. 2. P. 261294.

23. Berstel J. Recent results on Sturmian words // Developments in language theory II. Magdeburg, 1995. P. 13-24.

24. Berstel J., Perrin D. Finite and infinite words, in: M. Lothaire, Algebraic combinatorics on words, to appear.

25. Berstel J., Perrin D. Theory of codes. Academic Press, 1985.

26. Berthe V. Frequences des facteurs des suites sturmiennes // Theoret. Comput. Sci. 1996. V. 165, P. 295-309.

27. Brlek S. Enumeration of factors in the Thue-Morse word // Discrete Appl. Math. 1989. V. 24, P. 83-96.

28. Cassaigne J. An algorithm to test if a given circular HDOL-language avoids a pattern // Information processing'94. V. 1. Amsterdam: North-Holland, 1994. P. 459-464.

29. Cassaigne J. Complexite et facteurs speciaux // Bull. Belg. Math. Soc. 1997. V. 4, P. 67-88.

30. Cassaigne J. Limit values of the recurrence quotient of Sturmian sequences // Theoret. Comput. Sci. 1999. V. 218, P. 3-12.

31. Cassaigne J. Motifs evitables et regularites dans les mots // These de Doctorat. 1994. Universite Paris 6, Rapport LITP TH 94-04.

32. Cassaigne J. Sequences with grouped factors // Developments in Language Theory III. Thessaloniki, 1995. P. 211-222.

33. Cassaigne J. Unavoidable binary patterns // Acta Inf. 1993. V. 30.P. 385-395.

34. Cassaigne J., Karhumaki J. Toeplitz words, generalized periodicity and periodically iterated morphisms // European J. of Combinatorics. 1997. V. 18, P. 497-510.

35. Christol G., Kamae Т., Mendes Prance M., Rauzy G. Suites algebriques, automates et substitutions // Bull. Soc. Math. Prance. 1980, V. 108. P. 401-419.

36. Cobham A. Uniform tag sequences // Math. Systems Theory. 1972. V. 6, P. 164-192.

37. Crochemore M., Mignosi F., Restivo A., Salemi S. Data compression using antidictonaries // I.E.E.E., Lossless Data Compression, to appear.

38. Currie J. D. Open problems in pattern avoidance // Amer. Math. Monthly. 1993. V. 100. P. 790-793.

39. Dejean F. Sur un theoreme de Thue // J. Combin. Theory. Ser. A. 1972. V. 13, no. 1. P. 25-36.

40. Dekking M. On the Thue-Morse measure // Acta Univ. Carolin. Math. Phys. 1992. V. 33, No. 2. P. 35-40.

41. Ehrenfeucht A., Lee K. P., Rozenberg G. Subword complexities of various classes of deterministic developmental languages without interaction // Theoret. Comput. Sci. 1975. V. 1, P. 59-75.

42. Erdos P. Some unsolved problems // Magyar Tud. Akad. Mat. Kutato. Int. Kozl. 1961. V. 6, 221-254.

43. Ferenczi S. Complexity of sequences and dynamical systems // Discrete Math. 1999, V. 206, P. 145-154.

44. Ferenczi S., Mauduit C. Transcendence of numbers with a low complexity expansion // J. Number Th. 1997. V. 67, No. 2, P. 146161.

45. Frid A. E., Avgustinovich S. V. On bispecial words and subword complexity of DOL sequences // Sequences and Their Applications. London: Springer, 1999. P. 191-204.

46. Frid A. E. Applying a uniform marked morphism to a word // Discrete Mathematics and Theoretical Computer Science. 1999. V. 3, no. 3, P. 125-140.

47. Frid A. E. On the frequency of factors in a DOL word // J. Automata, Languages and Combinatorics. 1998. V. 3, No. 1. P. 29-41.

48. Frid A. E. On uniform DOL words // Theoretical Aspects of Computer Science. Berlin: Springer, 1998. P. 544-554. (Lecture Notes in Comput. Sci.; V. 1373).

49. Frid A. E. The subword complexity of fixed points of binary uniform morphisms // Fundamentals of Computation Theory. Berlin: Springer, 1997. P. 178-187. (Lecture Notes in Comput. Sci.; V. 1279).

50. Hall M. Generators and relations in groups — the Burnside problem. In: T. L. Saaty (ed.). Lectures on Moderm Mathematics. Wiley, 1964. V. 2, P. 42-92.

51. Hubert P. Complexite de suites definies par des billards rationnels // Bull. Soc. Math. Prance 1995. V. 123, P. 257-270.

52. Keranen V. Abelian squares are avoidable on 4 letters // Automata, Languages and Programming. Berlin: Springer, 1992. P. 41-52. (Lecture Notes in Comput. Sci.; V. 700).

53. Kolpakov R., Kucherov G., Tarannikov Yu. On repetition-free binary words of minimal density // Mathematical Foundations of Computer Science. Berlin: Springer, 1998. P. 683-692. (Lecture Notes in Comput. Sci.; V. 1450).

54. Koskas M. Complexites de suites de Toeplitz // Discrete Math. 1998. V. 183, P. 161-183.

55. Lothaire M. Combinatorics on words. Reading, Mass: Addison-Wesley, 1983.56. de Luca A., Varricchio S. Some combinatorial properties of the Thue-Morse sequence // Theoret. Comput. Sci. 1989. V. 63, P. 333348.

56. Mignosi F. On the number of factors of Sturmian words // Theoret. comput. Sci. 1991. V. 82, P. 71-84.

57. Mignosi F., Seebold P. If a D0L language is /с-power-free then it is circular // Automata, Languages and Programming. Berlin: Springer, 1993. P. 507-518. (Lecture Notes in Comput. Sci.; V. 700).

58. Morse M., Hedlund G. A. Symbolic dynamics II: Sturmian trajectories // Amer. J. Math. 1940. V. 61, P. 1-42.

59. Mosse В. Puissance de mots et reconnaissabilite des points fixes d'une substitution // Theoret. Comput. Sci. 1992. V. 99, P. 327334.

60. Mosse B. Reconnaissabilite des substitutions et complexite des suites automatiques // Bull. Soc. Math. Prance. 1996. V. 124, P. 329-346.

61. Nakashima I., Tamura J., Yasutomi S. Modified complexity and *-Sturmian word // Proc. Japan Acad. Ser. A. 1999. V. 75, P. 26-28.

62. Pansiot J.-J. Complexite des facteurs des mots infinis engendres par morphismes iteres // Automata, Languages and Programming. Berlin: Springer, 1984. P. 380-389. (Lecture Notes in Comput. Sci.; V. 172).

63. Queffelec M. Substitution dynamical systems — spectral analysis. Berlin: Springer, 1987. (Lecture Notes in Math., V. 1294).

64. Rote G. Sequences with subword complexity 2n // J. Number Th. 1994. V. 46, P. 196-213.

65. Tapsoba T. Automates calculant la complexite de suites automatiques // Journal de Theorie des Nombres de Bordeaux. 1994. V. 6, P. 127-134.

66. Thue A. Uber unendliche Zeichenreihen // Norske vid. Selsk. Skr. Mat. Nat. Kl., 1906. V. 7. P. 1-22.