arXiv Open Access 2018

Average Size of Implicational Bases

Giacomo Kahn Alexandre Bazin

Lihat Sumber

Abstrak

Implicational bases are objects of interest in formal concept analysis and its applications. Unfortunately, even the smallest base, the Duquenne-Guigues base, has an exponential size in the worst case. In this paper, we use results on the average number of minimal transversals in random hypergraphs to show that the base of proper premises is, on average, of quasi-polynomial size.

Topik & Kata Kunci

cs.AI cs.CC cs.DB math.CO

Penulis (2)

Giacomo Kahn

Alexandre Bazin

Format Sitasi

APA MLA BibTeX

Kahn, G., Bazin, A. (2018). Average Size of Implicational Bases. https://arxiv.org/abs/1802.04032

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2018
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓