List of issues > Series «Mathematics». 2009. Vol. 2
The complexity of RF-tests for repetition-free boolean functions
This paper contains the result of investigations in issues of testing of repetition-free Booleanfunctions(RF-test,forshort).Thetarget ofthispaperisobtaining the exact value of Shannon function for RF-tests. Our main results are: the exact value of Shannon function for RF-teststhe and the algorithm to construct fast RF-test for any repetition-free Boolean function.
1. ВороненкоА.A. Опроверяющихтестахдлябесповторныхфункций/ А.A. Вороненко // Математические вопросы кибернетики. — 2002. — Вып 11. — С. 163–176.
2. Вороненко А. А. О длине проверяющего теста для бесповторных функций в базисе {0,1, &,;∨,;¬} /А.А. Вороненко// Дискретнаяматематика. —2005. — Том 17. Выпуск 2. — С. 139–143.
3. Избранные вопросы теории булевых функций: Монография / А. С. Балюк,С. Ф. Винокуров, А. И. Гайдуков и др. Под ред. С. Ф. Винокурова, Н. А. Перязева. — М.: Физматлит, 2001. — 192 с.
4. Редькин Н. П. Надежностьидиагностикасхем/ Н. П.Редькин. — М.: Изд-во Моск. ун-та, 1992. — 192 с.
5. Рябец Л. В. Тестирование бесповторных булевых функций / А. С. Балюк, Л. В. Рябец // Вестник Томского государственного университета. Приложение.— 2006. — Вып 17. — С. 10–14.