Связи между решетками понятий и сложность их вычисления
Автор: Бабин Михаил Александрович, Кузнецов Сергей Олегович
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Математика, информатика, управление, экономика
Статья в выпуске: 2 (14) т.4, 2012 года.
Бесплатный доступ
В статье изучаются возможные типы связей между таксономиями предметных об- ластей, описываемыми в терминах решеток формальных понятий - наличие интенси- онально связанных понятий, общих содержаний, сцеплений. Исследована алгоритми- ческая сложность некоторых задач поиска связей. Получено выражение сцепления в виде общего формального содержания (замкнутого множества признаков).
Анализ формальных понятий, общие содержания, сцепления, вычислительная сложность
Короткий адрес: https://sciup.org/142185833
IDR: 142185833
On links between concept lattices and related complexity problems
Several notions of links between contexts, viz. intentionally related concepts, shared intents, and bonds, as well as interrelations thereof, are considered. The algorithmic complexity of the problems related to respective closure operators is studied. The expression of bonds in terms of shared intents is given.
Список литературы Связи между решетками понятий и сложность их вычисления
- Birkhoff G. Lattice Theory//Providence, RI: Amer. Math. Soc., 1967.
- Ganter B. and Wille R. Formal Concept Analysis: Mathematical Foundations. -Berlin: Springer, 1999.
- Ganter B. Lattices of Rough Set Abstractions as 𝑃-Products//Proc. International Conference on Formal Concept Analysis ICFCA 2008, LNCS (LNAI), 2008. -V. 4933. -P. 199-216.
- Garey M. and Johnson D. Computers and Intractability: A Guide to the Theory of NPCompleteness. -Freeman, San Francisco, 1979.
- Eiter T., Ibaraki T., Makino K. Computing Intersections of Horn Theories for Reasoning with Models//Proc. National Conference on Artificial Intelligence (AAAI'98), Madison, Wisconsin, 1998, July 26-30 -P. 292-297.
- Kuznetsov S.O. On Computing the Size of a Lattice and Related Decision Problems//Order, 2001. -N 18 -P. 313-321.
- Kuznetsov S.O. Obiedkov S.A., Comparing performance of algorithms for generating concept lattices//J. Exp. Theor. Artif. Intell., 2002. -V. 14, N 2-3. -P. 189-216.
- Kuznetsov S.O., On the Intractability of Computing the Duquenne-Guigues Base//Journal of Universal Computer Science, 2004. -V. 10, N 8. -P. 927-933.
- Kuznetsov S.O., Obiedkov S.A., Roth C. Reducing the Representation Complexity of Lattice-Based Taxonomies//Proc. 15th International Conference on Conceptual Structures (ICCS'07), LNAI, Springer, 2007. -V. 4604. -P. 241-254.
- Kr.otzsch M. and Malik G. The Tensor Product as a Lattice of Regular Galois Connections//Proc. 4th Inernational Conference on Formal Concept Analysis (ICFCA'2006), LNAI, Springer, 2006. -V. 3874. -P. 89-104.
- Wille R. Restructuring Lattice Theory: an Approach Based on Hierarchies of Concepts//Ordered Sets, Reidel, Dordrecht-Boston, 1982. -P. 445-470.
- Wille R. Conceptual Structure of Multicontexts//Proc. 4th International Conference on Conceptual Structures, LNAI, Springer, 1996. -V. 1115. -P. 23-39.
