Some structural properties of quadratic boolean threshold functions | Applied Discrete Mathematics. Supplement. 2015. № 8.

Some structural properties of quadratic boolean threshold functions

With the help of a binary partial order relation on the set of quadratic forms with Boolean variables, some classes of simultaneously decomposed (or not having any decompositions) quadratic Boolean threshold functions are described. Simple representatives of these classes are pointed out. In some cases, we can prove whether a variable is essential or not for a quadratic Boolean threshold functions.

Download file

Counter downloads: 270

Keywords

essential variable, decomposition, quadratic Boolean threshold function, существенная переменная, декомпозиция, квадратичная булева пороговая функция

Authors

Name	Organization	E-mail
Shurupov A.N.	MIREA (Moscow)	ashurupov@mail.ru

Всего: 1

References

Crama Y. and Hammer P. Boolean Functions. Theory, Algorithms and Applications. Cambridge University Press, 2011.

Dreo J., PetrowskiA., Siarry P., and TaillardE. Metaheuristics for Hard Optimisation. Methods and Case Studies. Springer, 2006. 372 p.

Хохлюк В. И. Прямой метод целочисленной оптимизации. Новосибирск: Ин-т математики им. С. Л. Соболева, 2002. 38с.

Хачиян Л. Г. Полиномиальный алгоритм в линейном программировании // Докл. АН СССР. 1979. Т. 244. №5. С. 1033-1096.

Шурупов А. Н. О функциональной разделимости булевых пороговых функций // Дискретная математика. 1997. Т. 9. Вып. 2. С. 59-73.

Подольский В. В. Оценки весов персептронов (полиномиальных пороговых булевых функций): автореф. дис.. канд. физ.-мат. наук. М.: МГУ им. М.В. Ломоносова, 2009.