Том 19, номер 6, 2012 г., Стр. 49-55

УДК 519.714
Мерекин Ю. В. 
Функция Шеннона вычисления сложности по Арнольду двоичных слов длины 2ⁿ

Аннотация:
Для предложенного автором ранее метода быстрого вычисления сложности по Арнольду произвольных двоичных слов длины 2ⁿ получено точное значение функции Шеннона для почти всех n.
Библиогр. 5.

Ключевые слова: двоичное слово, сложность слова, сложность по Арнольду, функция Шеннона.

Мерекин Юрий Владимирович ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: merekin@math.nsc.ru

Статья поступила 27 марта 2012 г.
Исправленный вариант — 23 августа 2012 г.

Литература

[1] Арнольд В. И. Топология и статистика формул арифметики // Успехи мат. наук. — 2003. — Т. 58, № 4. — c. 1–26.

[2] Мерекин Ю. В. О вычислении сложности по Арнольду двоичных слов // Мат. XVI Междунар. конф. «Проблемы теоретической кибернетики» (Нижний Новгород, 20–25 июня 2011 г.). — Нижний Новгород: Изд-во Нижегородск. гос. ун-та, 2011. — C. 315–319.

[3] Merekin Yu. V. On the computational complexity of the Arnold complexity of binary words // Asian-Eur. J. Math. — 2009. — Vol. 2, N 4. — P. 641–648.

[4] Merekin Yu. V. On the computation of Arnold complexity of length $2^n$ binary words // Asian-Eur. J. Math. — 2011. — Vol. 4, N 2. — P. 295–300.

[5] Merekin Yu. V. Fast computation of the Arnold complexity of length $2^n$ binary words // ArXive e-print arXiv:1209.4700[mathCO], 2012.