Approximating minimum representations of key Horn functions

Autor:	Kristóf Bérczi, Endre Boros, Ondřej Čepek, Petr Kučera, Kazuhisa Makino
Jazyk:	angličtina
Rok vydání:	2018
Předmět:	FOS: Computer and information sciences TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES General Computer Science Computer Science - Databases General Mathematics Computer Science - Data Structures and Algorithms Data Structures and Algorithms (cs.DS) Databases (cs.DB)
Popis:	Horn functions form a subclass of Boolean functions and appear in many different areas of computer science and mathematics as a general tool to describe implications and dependencies. Finding minimum sized representations for such functions with respect to most commonly used measures is a computationally hard problem that remains hard even for the important subclass of key Horn functions. In this paper we provide logarithmic factor approximation algorithms for key Horn functions with respect to all measures studied in the literature for which the problem is known to be hard. 23 pages
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f249584a004ee5caef0f55b831cb7497 http://arxiv.org/abs/1811.05160 Zobrazit plný text záznamu