Dualization in lattices given by ordered sets of irreducibles

M. A. Babin; S. Kuznetsov

doi:10.1016/j.tcs.2016.01.005

Публикации

?

Dualization in lattices given by ordered sets of irreducibles

Theoretical Computer Science. 2017. Vol. Volume 658, Part B. No. 7 January. P. 316–326.

Бабин М. А., Кузнецов С. О.

Dualization of a monotone Boolean function on a finite lattice can be represented by transforming the set of its minimal 1 values 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.

Язык: английский

Полный текст

DOI

Ключевые слова: Formal Concept Analysis Distributive lattice Monotone Boolean dualization

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:

Хорошо интерпретируемые методы интеллектуального анализа семантически насыщенных данных и их приложения (2017)

Is Canfield Right? On the Asymptotic Coefficients for the Maximum Antichain of Partitions and Related Counting Inequalities

Игнатов Д. И., , in: 11th International Conference, AIST 2023, Yerevan, Armenia, September 28–30, 2023, Revised Selected Papers. Analysis of Images, Social Networks and Texts. Lecture Notes in Computer Science (LNCS, volume 14486).: Cham: Springer, 2024. P. 349 – 361.

Добавлено: 23 января 2026 г.

Combinatorics behind discriminants of polynomial systems

Покидкин В. П., / Series math "arxiv.org". 2025.

В 1970-ые годы Кушниренко, Бернштейн и Хованский заметили, что геометрия общих полиномиальных систем уравнений определяется геметрией соответствующих многогранников Ньютона. В 1990-ые годы Гельфанд, Капранов, Зелевинский и Штурмфельс обобщили это наблюдение для дискриминантов и результантов полиномов общего положения. В частности, хорошо известные открытые вопросы о неприводимости дискриминантов и множеств решений таких полиномиальных систем свелись к геометрическому ...

Добавлено: 4 сентября 2025 г.

Object-Attribute Biclustering for Elimination of Missing Genotypes in Ischemic Stroke Genome-Wide Data

Игнатов Д. И., Khvorykh G., Khrunin A. и др., , in: Recent Trends in Analysis of Images, Social Networks and Texts. 9th International Conference, AIST 2020, Skolkovo, Moscow, Russia, October 15–16, 2020 Revised Supplementary ProceedingsVol. 12602.: Springer, 2021. P. 185–204.

Добавлено: 1 ноября 2022 г.

Triclusters of Close Values for the Analysis of 3D Data

Егурнов Д. А., Игнатов Д. И., Automation and Remote Control 2022 Vol. 83 No. 6 P. 894–902

Добавлено: 1 ноября 2022 г.

Proceedings of the Fifthteenth International Conference on Concept Lattices and Their Applications

CEUR-WS.org, 2020.

Добавлено: 30 октября 2020 г.

Condorcet Domains, Median Graphs and the Single-Crossing Property

Пуппе К. Д., Slinko A., Economic Theory 2019 Vol. 67 No. 1 P. 285–318

Добавлено: 18 мая 2020 г.

L-models and R-models for Lambek calculus enriched with additives and the multiplicative unit

Канович М. И., Кузнецов С. Л., Щедров А., , in: Logic, Language, Information, and Computation: 26th International Workshop, WoLLIC 2019, Utrecht, The Netherlands, July 2-5, 2019, ProceedingsVol. 11541: Lecture Notes in Computer Science.: Berlin, Heidelberg: Springer, 2019. P. 373–391.

Добавлено: 4 сентября 2019 г.

CLA 2018: The 14th International Conference on Concept Lattices and Their Applications

CEUR Workshop Proceedings, 2018.

Добавлено: 25 ноября 2018 г.

Multimodal Clustering for Community Detection

Игнатов Д. И., Семенов А. В., Комиссарова Д. В. и др., , in: Formal Concept Analysis of Social Networks.: Springer, 2017. Ch. 4 P. 59–96.

Добавлено: 17 декабря 2017 г.

Formal Concept Analysis for Knowledge Discovery. Proceedings of International Workshop on Formal Concept Analysis for Knowledge Discovery (FCA4KD 2017), Moscow, Russia, June 1, 2017.

CEUR-WS.org, 2017.

Добавлено: 4 октября 2017 г.

Query-Based Versus Tree-Based Classification: Application to Banking Data

Масютин А. А., Кашницкий Ю. С., , in: Foundations of Intelligent Systems.: Warsz.: Springer, 2017. P. 664–673.

The cornerstone of retail banking risk management is the estimation of the expected losses when granting a loan to the borrower. The key driver for loss estimation is probability of default (PD) of the borrower. Assessing PD lies in the area of classification problem. In this paper we apply FCA query-based classification techniques to Kaggle ...

Добавлено: 6 июля 2017 г.

14th International Conference on Formal Concept Analysis - Supplementary Proceedings

University Rennes 1, 2017.

This volume is the supplementary volume of the 14th International Conference on Formal Concept Analysis (ICFCA 2017), held from June 13th to 16th 2017, at IRISA, Rennes. The ICFCA conference series is one of the major venues for researches from the field of Formal Concept Analysis and related areas to present and discuss their recent ...

Добавлено: 19 июня 2017 г.

Approximate clusters, biclusters and n-clusters in the analysis of binary and general data matrices

Миркин Б. Г., , in: CLA 2016: Proceedings of the Thirteenth International Conference on Concept Lattices and Their Applications. CEUR Workshop ProceedingsVol. 1624.: M.: Higher School of Economics, National Research University, 2016. P. 7–8.

Аpproximate cluster structures are those of formal concepts and n-concepts with added numerical intensity weights. The talk presents theoretical results and computational methods for approximate clustering and n-clustering as extensions of the algebraic-geometrical properties of numerical matrices (SVD and the like) to the situations where one or most of elements of the solutions to be ...

Добавлено: 3 марта 2017 г.

A Lattice-based Consensus Clustering Algorithm

Бочаров А. А., Гнатышак Д. В., Игнатов Д. И. и др., , in: CLA 2016: Proceedings of the Thirteenth International Conference on Concept Lattices and Their Applications. CEUR Workshop ProceedingsVol. 1624.: M.: Higher School of Economics, National Research University, 2016. P. 45–56.

Добавлено: 24 октября 2016 г.

On Stability of Triadic Concepts

Кузнецов С. О., Махалова Т. П., , in: CLA 2016: Proceedings of the Thirteenth International Conference on Concept Lattices and Their Applications. CEUR Workshop ProceedingsVol. 1624.: M.: Higher School of Economics, National Research University, 2016. P. 245–253.

Добавлено: 11 октября 2016 г.

Interval Pattern Concept Lattice as a Classifier Ensemble

Кашницкий Ю. С., Кузнецов С. О., , in: Proceedings of the International Workshop "What can FCA do for Artificial Intelligence?" (FCA4AI at ECAI 2016).: M.: [б.и.], 2016. P. 105–112.

Decision tree learning is one of the most popular classifica- tion techniques. However, by its nature it is a greedy approach to finding a classification hypothesis that optimizes some information-based crite- rion. It is very fast but may lead to finding suboptimal classification hy- potheses. Moreover, in spite of decision trees being easily interpretable, ensembles ...

Добавлено: 6 октября 2016 г.

Proceedings of the International Workshop "What can FCA do for Artificial Intelligence?" (FCA4AI at ECAI 2016)

M.: [б.и.], 2016.

The four preceding editions of the FCA4AI Workshop showed that many researchers working in Artificial Intelligence are deeply interested by a well-founded method for classi- fication and mining such as Formal Concept Analysis (see http://www.fca4ai.hse.ru/). The first edition of FCA4AI was co-located with ECAI 2012 in Montpellier, the second one with IJCAI 2013 in Beijing, ...

Добавлено: 6 октября 2016 г.

Global Optimization in Learning with Important Data: an FCA-Based Approach

Кашницкий Ю. С., Кузнецов С. О., , in: CLA 2016: Proceedings of the Thirteenth International Conference on Concept Lattices and Their Applications. CEUR Workshop ProceedingsVol. 1624.: M.: Higher School of Economics, National Research University, 2016. Ch. 19 P. 189–202.

Nowadays decision tree learning is one of the most popular classification and regression techniques. Though decision trees are not accurate on their own, they make very good base learners for advanced tree-based methods such as random forests and gradient boosted trees. However, applying ensembles of trees deteriorates interpretability of the final model. Another problem is ...

Добавлено: 6 октября 2016 г.

CLA 2016: Proceedings of the Thirteenth International Conference on Concept Lattices and Their Applications. CEUR Workshop Proceedings

M.: Higher School of Economics, National Research University, 2016.

The 13th International Conference on “Concept Lattices and Applications (CLA 2016)” was held at National Research University Higher School of Economics, Moscow, Russia from July 18 until July 22, 2016. The CLA conference, organized since 2002, aims to provide to everyone interested in Formal Concept Analysis and more generally in Concept Lattices or Galois Lattices, ...

Добавлено: 6 октября 2016 г.

Lazy Learning of Succinct Classification Rules for Complex Structure Data

Кашницкий Ю. С., , in: Supplementary Proceedings of the 5th International Conference on Analysis of Images, Social Networks and Texts (AIST-SUP 2016), Yekaterinburg, Russia, April 7-9, 2016.Vol. 1710.: Aachen: CEUR Workshop Proceedings, 2016. Ch. 8 P. 73–84.

In this paper, we address machine learning classification problem and classify each test instance with a set of interpretable and accurate rules. We resort to the idea of lazy classification and mathematical apparatus of formal concept analysis to develop an abstract framework for this task. In a set of benchmarking experiments, we compare the proposed ...

Добавлено: 6 октября 2016 г.

Browsing publication data using tag clouds over concept lattices constructed by key-phrase extraction

Greene G., Dunaiski M., Fischer B. и др., , in: RuZA 2015 Workshop. Proceedings of Russian and South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis (RuZA 2015). November 30 - December 5, 2015, Stellenbosch, South AfricaVol. 1552.: Aachen: CEUR Workshop Proceedings, 2015. P. 10–22.

Добавлено: 14 июня 2016 г.

Full-text Search in Intermediate Data Storage of FCART

Незнанов А. А., Паринов А. А., , in: RuZA 2015 Workshop. Proceedings of Russian and South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis (RuZA 2015). November 30 - December 5, 2015, Stellenbosch, South AfricaVol. 1552.: Aachen: CEUR Workshop Proceedings, 2015.

The speed of full-text search directly affects the process of text analysis. Search engine creates a text index, which is used for fast full-text search. Solr and ElasticSearch are two popular search engines. A text analysis system requires fast implementing searching and indexing at the same time. This paper describes preprocessing workflow of the analysis ...

Добавлено: 14 июня 2016 г.