Том 17, номер 6, 2010 г., Стр. 20-49
УДК 510.53
Вялый М. Н., Тарасов С. П.
Орбиты линейных отображений и свойства регулярных языков
Аннотация:
Установлена эквивалентность задачи о протыкании полиэдрального множества орбитой линейного отображения и задачи о пересечении регулярного языка с языком перестановок двоичных слов (перестановочным фильтром). Алгоритмическая разрешимость для обеих задач неизвестна. Первая из них обобщает хорошо известные открытые проблемы Сколема и неотрицательности, относящиеся к линейным рекуррентным последовательностям.
Библиогр. 14.
Ключевые слова: линейная рекуррентная последовательность, линейное отображение, орбита, регулярный язык, алгоритмическая разрешимость.
Вялый Михаил Николаевич 1
Тарасов Сергей Павлович 1
1. Вычислительный центр РАН,
ул. Вавилова, 40, 119333 Москва, Россия
е-mail: vyalyi@gmail.com, serge99meister@gmail.com
Статья поступила 11 мая 2010 г.
