ИСТИНА

Слово ..abababa.. можно однозначно с точностью до сдвига задать запретив подслова {aa, bb}, слово ..aabaab.. — {aaa, bb, bab} Исследуется зависимость длины наименьшего периода от количества запретов. (понятно, что период характеризует сложность слова, а размер системы запретов — сложность его описания) Получена точная (с примером) оценка для количества запретов слов в двухсимвольном алфавите {a, b}: |S| >= log_\alpha(n), где S — запреты, n — наименьший период слова, \alpha = \frac{1+\sqrt(5)}{2} — золотое сечение, а также асимптотическая — с точностью до константы — в случае k-буквенного алфавита (|S| >= log_\alpha(n)-C(k)), которая, как легко показывается — тоже точна. В решении строится последовательность графов, связанных некоторыми правилами эволюции, размер конечного из которых равен периоду слова и оценивается их рост в процессе эволюции.