Positive and Horn decomposability of partially defined Boolean functions

Autor:	Kazuhisa Makino, Toshihide Ibaraki, Kojin Yano
Rok vydání:	1997
Předmět:	Combinatorics Discrete mathematics French horn Efficient algorithm Applied Mathematics Line (geometry) Discrete Mathematics and Combinatorics Boolean expression Boolean function Mathematics
Zdroj:	Discrete Applied Mathematics. 74(3):251-274
ISSN:	0166-218X
DOI:	10.1016/s0166-218x(96)00053-4
Popis:	We consider the decomposability of partially defined Boolean functions under given schemes, along the line developed in [2]. For two positive schemes, whose complexity was left open in [2], we prove their NP-completeness. We then consider Horn schemes and mixed schemes (mixture of positive and Horn functions), and obtain computationally efficient algorithms in some cases, but prove NP-completeness in other cases.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f0c946f73117610724094ba2b7c4219e Zobrazit plný text záznamu Full Text from ScienceDirect