М. Н. Вялый, С. П. Тарасов, “Орбиты линейных отображений и свойства регулярных языков”, Дискретн. анализ и исслед. опер., 2010, том 17, выпуск 6,страницы 20

Эта публикация цитируется в 6 статьях

Орбиты линейных отображений и свойства регулярных языков

М. Н. Вялый, С. П. Тарасов

Вычислительный центр РАН, Москва, Россия

Аннотация: Установлена эквивалентность задачи о протыкании полиэдрального множества орбитой линейного отображения и задачи о пересечении регулярного языка с языком перестановок двоичных слов (перестановочным фильтром). Алгоритмическая разрешимость для обеих задач неизвестна. Первая из них обобщает хорошо известные открытые проблемы Сколема и неотрицательности, относящиеся к линейным рекуррентным последовательностям. Библиогр. 14.

Ключевые слова: линейная рекуррентная последовательность, линейное отображение, орбита, регулярный язык, алгоритмическая разрешимость.

УДК: 510.53

Статья поступила: 11.05.2010