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:

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}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2018},
NUMBER = {TR-2018-12}

Last modification: 29.12.2020. Please email your comments to Tamás Király!