کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949515 1440193 2017 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Optimum basis of finite convex geometry
ترجمه فارسی عنوان
پایه بهینه هندسه محدب محدود
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Convex geometries form a subclass of closure systems with unique criticals, or UC-systems. We show that the F-basis introduced in Adaricheva and Nation (2014) for UC-systems, becomes optimum in convex geometries, in two essential parts of the basis: right sides (conclusions) of binary implications and left sides (premises) of non-binary ones. The right sides of non-binary implications can also be optimized, when the convex geometry either satisfies the Carousel property, or does not have D-cycles. The latter generalizes a result of P.L. Hammer and A. Kogan for acyclic Horn Boolean functions. Convex geometries of order convex subsets in a poset also have tractable optimum basis. The problem of tractability of optimum basis in convex geometries in general remains to be open.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 230, 30 October 2017, Pages 11-20
نویسندگان
,