|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
О свойствах полиномов периодических функций и сложности распознавания периодичности по полиному булевой функциистатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКДата последнего поиска статьи во внешних источниках: 28 мая 2015 г.
- Автор: Бухман А.В.
- Журнал: Дискретная математика
- Том: 26
- Номер: 1
- Год издания: 2014
- Издательство: ФГБУ "Издательство "Наука"
- Местоположение издательства: Москва
- Первая страница: 21
- Последняя страница: 31
- DOI: 10.4213/dm1265
- Аннотация: В статье исследуется вопрос об алгоритмической сложности распознавания периодичности булевых функций, заданных полиномами. Функция называется периодической с периодом τ, если она не изменяется при подстановке вместо всех переменных, соответствующих 1 в векторе τ, их отрицаний. Построено два полиномиальных алгоритма проверки того, что заданный вектор является периодом булевой функции. Исследована связь периода функции и длины её полинома. Построено в явном виде полиномиальное сведение задачи о поиске периода к решению системы булевых уравнений. Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 13-01-00684.
- Добавил в систему: Бухман Антон Владимирович