Dualization in Lattices Given by Implicational Bases
| Autor: | Lhouari Nourine, Oscar Defrain |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Property (philosophy)
Matching (graph theory) 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 16. Peace & justice 01 natural sciences Combinatorics Base (group theory) Distributive property 010201 computation theory & mathematics Lattice (order) Bounded function 0202 electrical engineering electronic engineering information engineering Graph (abstract data type) Interval order Mathematics |
| Zdroj: | Formal Concept Analysis ISBN: 9783030214616 ICFCA |
| DOI: | 10.1007/978-3-030-21462-3_7 |
| Popis: | It was recently proved that the dualization in lattices given by implicational bases is impossible in output-polynomial time unless \(\mathsf{P}\!=\!\mathsf{NP}\). In this paper, we show that this result holds even when the premises in the implicational base are of size at most two. In the case of premises of size one—when the lattice is distributive—we show that the dualization is possible in output quasi-polynomial time whenever the graph of implications is of bounded maximum induced matching. Lattices that share this property include distributive lattices coded by the ideals of an interval order. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|