Some decision and counting problems of the Duquenne-Guigues basis of implications |
| |
| Authors: | Sergei O Kuznetsov |
| |
| Institution: | a Department of Applied Mathematics, State University Higher School of Economics, Moscow, Russia
b Department of Computer Science, University of Pretoria, Pretoria, South Africa |
| |
| 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. |
| |
| Keywords: | Implication basis Duquenne-Guigues basis #P-completeness Functional dependencies |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
