@johirth

Some decision and counting problems of the Duquenne-Guigues basis of implications

, and . Discrete Appl. Math. 156 (11): 1994--2003 (2008)

Abstract

Implications of a formal context obey Armstrong rules, which allows one to define a minimal (in the number of implications) implication basis, called Duquenne-Guigues basis or stem base in the literature. In this paper we show how implications are reduced to functional dependencies and prove that the problem of determining the size of the stem base is a #P-complete problem.

Description

Some decision and counting problems of the Duquenne-Guigues basis of implications

Links and resources

DOI:
10.1016/j.dam.2007.04.014
URL:
BibTeX key:
1393768
search on:

Comments and Reviews  
(0)

There is no review or comment yet. You can write one!

Tags


Cite this publication