Dualization in lattices given by ordered sets of irreducibles

DOI10.1016/J.TCS.2016.01.005zbMATH Open1356.68225arXiv1504.01145OpenAlexW2963150415MaRDI QIDQ507520FDOQ507520

Authors: Mikhail A. Babin, Sergei O. Kuznetsov 

Publication date: 6 February 2017

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

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.

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

Recommendations

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The relative complexity of approximate counting problems
• Lattice Theory: Foundation
• Title not available (Why is that?)
• Generating all maximal models of a Boolean expression
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Complexity of learning in concept lattices from positive and negative examples
• Computational aspects of monotone dualization: a brief survey
• Structure identification in relational data
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms for dualization over products of partially ordered sets
• Hypotheses and version spaces
• Mathematical aspects of concept analysis
• Some decision and counting problems of the Duquenne-Guigues basis of implications

Cited In (11)

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

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)