Dualization in lattices given by ordered sets of irreducibles

DOI10.1016/J.TCS.2016.01.005MaRDI QIDQ507520zbMATH OpenOpenAlexFDO

Authors Mikhail A. Babin, Sergei O. Kuznetsov

Publication date 6 February 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.01145

zbMATH Keywords

formal concept analysisdistributive latticemonotone Boolean dualization

Mathematics Subject Classification ID

Knowledge representation (68T30) Nonnumerical algorithms (68W05) Galois correspondences, closure operators (in relation to ordered sets) (06A15) Complete lattices, completions (06B23) Boolean functions (06E30)

Abstract: 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.

Recommendations

• Enumerating minimal hypotheses and dualizing monotone Boolean functions on lattices
• On the dualization in distributive lattices and related problems
• On the complexity of the dualization problem

Cites work

• scientific article; zbMATH DE number 6519673 (Why is no real title available?)
• scientific article; zbMATH DE number 3823743 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1249514 (Why is no real title available?)
• scientific article; zbMATH DE number 1947411 (Why is no real title available?)
• scientific article; zbMATH DE number 1748069 (Why is no real title available?)
• scientific article; zbMATH DE number 2086381 (Why is no real title available?)
• scientific article; zbMATH DE number 861622 (Why is no real title available?)
• scientific article; zbMATH DE number 7635224 (Why is no real title available?)
• Algorithms for dualization over products of partially ordered sets
• Complexity of learning in concept lattices from positive and negative examples
• Computational aspects of monotone dualization: a brief survey
• Generating all maximal models of a Boolean expression
• Hypotheses and version spaces
• Lattice Theory: Foundation
• Mathematical aspects of concept analysis
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Some decision and counting problems of the Duquenne-Guigues basis of implications
• Structure identification in relational data
• The relative complexity of approximate counting problems

Cited in

(10)

• Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements
• Translating between the representations of a ranked convex geometry
• On the dual Helly number and irreducible decompositions of the unit in lattices
• On the dualization in distributive lattices and related problems
• Enumerating maximal consistent closed sets in closure systems
• On Dualization over Distributive Lattices
• Dualities between complete lattices
• Extended dualization: application to maximal pattern mining
• Enumerating minimal hypotheses and dualizing monotone Boolean functions on lattices
• scientific article; zbMATH DE number 3887755 (Why is no real title available?)

This page was built for publication: Dualization in lattices given by ordered sets of irreducibles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507520)