TR-2018-12

Minimal representation of elementary Horn functions

Kristóf Bérczi, Endre Boros, Ondrej Cepek, Petr Kucera, Kazuhisa Makino

Horn functions form a computationally tractable subclass of Boolean functions and appear in many different areas of computer science and mathematics as a general tool to describe implications and dependencies. The problem of finding a minimum representation of a Horn function is interesting both from a theoretical and a practical viewpoint. We give approximation algorithms for the problem in a special class of Horn functions.

Bibtex entry:

@techreport{egres-18-12,

AUTHOR	=	{B{\'e}rczi, Krist{\'o}f and Boros, Endre and Cepek, Ondrej and Kucera, Petr and Makino, Kazuhisa},
TITLE	=	{Minimal representation of elementary Horn functions},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2018},
NUMBER	=	{TR-2018-12}

}