
arXiv: 1504.01145
Dualization of a monotone Boolean function on a finite lattice can be represented by transforming the set of its minimal 1 to the set of its maximal 0 values. In this paper we consider finite lattices given by ordered sets of their meet and join irreducibles (i.e., as a concept lattice of a formal context). We show that in this case dualization is equivalent to the enumeration of so-called minimal hypotheses. In contrast to usual dualization setting, where a lattice is given by the ordered set of its elements, dualization in this case is shown to be impossible in output polynomial time unless P = NP. However, if the lattice is distributive, dualization is shown to be possible in subexponential time.
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Discrete Mathematics (cs.DM), Computational Complexity (cs.CC), Galois correspondences, closure operators (in relation to ordered sets), distributive lattice, monotone Boolean dualization, Logic in Computer Science (cs.LO), formal concept analysis, Computer Science - Computational Complexity, Knowledge representation, Complete lattices, completions, Boolean functions, Nonnumerical algorithms, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Discrete Mathematics (cs.DM), Computational Complexity (cs.CC), Galois correspondences, closure operators (in relation to ordered sets), distributive lattice, monotone Boolean dualization, Logic in Computer Science (cs.LO), formal concept analysis, Computer Science - Computational Complexity, Knowledge representation, Complete lattices, completions, Boolean functions, Nonnumerical algorithms, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 8 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
