TR-2018-12

Minimal representation of elementary Horn functions

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



Abstract

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 www.cs.elte.hu/egres}},
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!