کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949832 | 1364259 | 2017 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The splitting technique in monotone recognition
ترجمه فارسی عنوان
تکنیک تقسیم در تشخیص یکنواخت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تابع بولی تابع توری، به رسمیت شناختن،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider the problem of query based algorithmic identification/recognition of monotone Boolean functions, as well as of binary functions defined on multi-valued discrete grids. Hansel's chain-split technique of n-cubes is a well known effective tool of monotone Boolean recognition. An extension by Alekseev is already applied to the grid case. The practical monotone recognition on n-cubes is provided by the so called chain-computation algorithms that is not extended to the case of multi-valued grids. We propose a novel split construction based on partitioning the grid into sub-grids and into discrete structures that are isomorphic to binary cubes. Monotonicity in a multi-valued grid implies monotonicity in all induced binary cubes and in multi-valued sub-grids. Applying Hansel's technique for identification of monotone Boolean functions on all appearing binary cubes, and Alekseev's algorithm on all sub-grids leads to different scenarios of reconstruction of monotone functions. On one hand such partitioning technique makes parallel recognition possible, on the other hand - the method can be used in practical identification algorithms due to simple structures and easily calculable quantities appearing after the partition to the n-cubes. Complexity issues of considered algorithms were also elaborated.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 216, Part 3, 10 January 2017, Pages 502-512
Journal: Discrete Applied Mathematics - Volume 216, Part 3, 10 January 2017, Pages 502-512
نویسندگان
L. Aslanyan, H. Sahakyan,