Сложность языка поворотов двух дуг. Краткое сообщение
Автор: Решетников И.А.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Информатика и управление
Статья в выпуске: 3 (51) т.13, 2021 года.
Бесплатный доступ
Работа посвящена изучению количества слов длины n, порождаемых повротами всевозможных двух дуг окружности на фиксированный иррациональный угол поворота 𝜀. В работе [1] (см. также [2]) получена кубическая оценка для арифметической сложности слов Штурма, откуда следует и кубическая оценка для количества слов, порождаемых поворотами двух дуг. В данной работе угол поворота предполагается фиксированным, в результате чего оценка на количество слов длины n получается квадратичной от n.
Слова штурма, арифметическая сложность, механические слова, динамические системы, поворот окружности, символическая динамика
Короткий адрес: https://sciup.org/142231005
IDR: 142231005 | DOI: 10.53815/20726759_2021_13_3_107
Список литературы Сложность языка поворотов двух дуг. Краткое сообщение
- Фрид А.Э. Нижняя оценка на арифметическую сложность слов Штурма // Сиб. электрон. матем. изв. 2005. N 2. С. 14-22.
- Cassaigne J., Frid A.E. On the arithmetical complexity of Sturmian words // Theoret. Comput. Sci. 2007. N 3. P. 304-31.
