Dualization in lattices given by implicational bases
| Autor: | Lhouari Nourine, Oscar Defrain |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Centre National de la Recherche Scientifique (CNRS), Université Clermont Auvergne (UCA), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) General Computer Science 0102 computer and information sciences 02 engineering and technology [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 16. Peace & justice 01 natural sciences Graph Theoretical Computer Science Combinatorics Distributive property 010201 computation theory & mathematics Bounded function Lattice (order) Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) 020201 artificial intelligence & image processing Interval order ComputingMilieux_MISCELLANEOUS Computer Science - Discrete Mathematics Mathematics |
| Zdroj: | Theoretical Computer Science Theoretical Computer Science, Elsevier, 2020, 814, pp.169-176. ⟨10.1016/j.tcs.2020.01.028⟩ Theoretical Computer Science, 2020, 814, pp.169-176. ⟨10.1016/j.tcs.2020.01.028⟩ |
| ISSN: | 1879-2294 0304-3975 |
| DOI: | 10.1016/j.tcs.2020.01.028⟩ |
| Popis: | It was recently proved that the dualization in lattices given by implicational bases is impossible in output-polynomial time unless P=NP. In this paper, we~show that this result holds even when the premises in the implicational base are of size at most two. Then we show using hypergraph dualization that the problem can be solved in output quasi-polynomial time whenever the implicational base has bounded independent-width, defined as the size of a maximum set of implications having independent conclusions. Lattices that share this property include distributive lattices coded by the ideals of an interval order, when both the independent-width and the size of the premises equal one. Comment: 11 pages, 2 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect