检索结果-内蒙古大学图书馆

Enumerating and categorizing positive boolean functions separable by a k-additive capacity

DISCRETE APPLIED MATHEMATICS 2017年 229卷 17-30页

作者： Uyanik, Eda Sobrie, Olivier Mousseau, Vincent Pirlot, Marc CentraleSupelec F-92295 Chatenay Malabry France Univ Mons Fac Polytech 9 Rue Houdain B-7000 Mons Belgium

Motivated by the elicitation or the learning of certain types of models for classifying objects in ordered categories based on several criteria, we categorize the positive boolean functions up to 6 variables. We list all inequivalent positive boolean functions and we determine the smallest degree k of the k-additive capacity that can be used for separating their true points from their false points. 1-additive boolean functions are the well-studied threshold functions. Each function is described by its set of minimal true points. The latter correspond to the minimal winning coalitions of simple games. They also correspond to the minimal sufficient coalitions in the multiple criteria classification models we are interested in, namely, the MR-Sort and the noncompensatory sorting model. (c) 2017 Elsevier B.V. All rights reserved.

关键词： Multiple criteria sorting methods positive boolean functions Ordered classification Winning coalitions k-additive capacity

来源：评论

学校读者我要写书评

暂无评论

Gene expression modeling through positive boolean functions

引用

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING 2008年第1期47卷 97-108页

作者： Ruffino, Francesca Muselli, Marco Valentini, Giorgio Univ Milan Dipartimento Sci Informaz DSI Milan Italy CNR IEIIT Genoa Italy

In the framework of gene expression data analysis, the selection of biologically relevant sets of genes and the discovery of new subclasses of diseases at bio-molecular level represent two significant problems. Unfortunately, in both cases the correct solution is usually unknown and the evaluation of the performance of gene selection and clustering methods is difficult and in many cases unfeasible. A natural approach to this complex issue consists in developing an artificial model for the generation of biologically plausible gene expression data, thus allowing to know in advance the set of relevant genes and the functional classes involved in the problem. In this work we propose a mathematical model, based on positive boolean functions, for the generation of synthetic gene expression data. Despite its simplicity, this model is sufficiently rich to take account of the specific peculiarities of gene expression, including the biological variability, viewed as a sort of random source. As an applicative example, we also provide some data simulations and numerical experiments for the analysis of the performances of gene selection methods. (c) 2007 Elsevier Inc. All rights reserved.

关键词： gene expression modeling gene selection gene expression data clustering positive boolean functions DNA microarrays

来源：评论

学校读者我要写书评

暂无评论

Stack filter design using selection probabilities

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2005年第3期53卷 1025-1037页

作者： Prasad, MK Freescale Semicond Wireless Solut Div Austin TX 78733 USA

Selection probabilities, viz. rank and sample selection probabilities, quantify the impulse suppression, robustness, low-pass filtering ability, and detail preserving ability of stack filters. Closed-form expressions exist for computing selection probabilities from positive boolean function describing the stack filter. In this paper, we first present an analysis framework that interprets a boolean vector to denote membership in a partition set. Using this framework a new algorithm to compute selection probabilities from positive boolean functions is derived. Next a method to synthesize a stack filter from specified selection probabilities is presented. An underdetermined system of linear Diophantine equations is derived in the unknown elements of the C-matrix and the desired selection probabilities. This system of equations is solved to obtain the candidate solutions for the C-matrix. For each candidate C-matrix, an algorithm based on partition sets is used to derive one or more positive boolean functions of the stack filter or show that none exists.

关键词： analysis and synthesis of stack filters design of stack filters partition sets positive boolean functions selection probabilities stack filters

来源：评论

学校读者我要写书评

暂无评论

A simple polynomial groundness analysis for logic programs

引用

JOURNAL OF LOGIC PROGRAMMING 2000年第1-3期45卷 143-156页

作者： Heaton, A Abo-Zaed, M Codish, M King, A Univ Kent Comp Lab Canterbury CT2 7NF Kent England Univ Melbourne Dept Comp Sci & Software Engn Parkville Vic 3052 Australia Ben Gurion Univ Negev Dept Math & Comp Sci IL-84105 Beer Sheva Israel Univ Leeds Sch Comp Studies Leeds LS2 9JT W Yorkshire England

The domain of positive boolean functions, Pos, is by now well established for the analysis of the variable dependencies that arise within logic programs. Analyses based on Pos that use binary decision diagrams (BDDs) have been shown to be efficient for a wide range of practical programs. However, independent of the representation, a Pos analysis can never come with any efficiency guarantees because of its potential exponential behaviour. This paper considers groundness analysis based on a simple subdomain of Pos and compares its precision with that of Pos. (C) 2000 Elsevier Science Inc. All rights reserved.

关键词： groundness analysis positive boolean functions

来源：评论

学校读者我要写书评

暂无评论

Minimum self-dual decompositions of positive dual-minor boolean functions

引用

DISCRETE APPLIED MATHEMATICS 1999年 97卷 307-326页

作者： Bioch, JC Ibaraki, T Makino, K Kyoto Univ Grad Sch Engn Dept Appl Math & Phys Kyoto 6068501 Japan Erasmus Univ Dept Comp Sci NL-3000 DR Rotterdam Netherlands Osaka Univ Grad Sch Engn Sci Dept Syst & Human Sci Osaka 5608531 Japan

In this paper we consider decompositions of a positive dual-minor boolean function f into f = f(1)f(2),...,f(k), where all f, are positive and self-dual. It is shown that the minimum k having such a decomposition equals the chromatic number of a graph associated with f, and the problem of deciding whether a decomposition of size k exists is co-NP-hard, for k greater than or equal to 2. We also consider the canonical decomposition of f and show that the complexity of finding a canonical decomposition is equivalent to deciding whether two positive boolean functions are mutually dual. Finally, for the class of path functions including the class of positive read-once functions, we show that the sizes of minimum decompositions and minimum canonical decompositions are equal, and present a polynomial total time algorithm to generate all minimal canonical decompositions. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： coteries games positive boolean functions monotone boolean functions self-dual functions decompositions of positive dual-minor functions path functions read-once functions

来源：评论

学校读者我要写书评

暂无评论

Image and signal processing with mathematical morphology

引用

ELECTRONICS & COMMUNICATION ENGINEERING JOURNAL 1998年第3期10卷 117-128页

作者： Bangham, JA Marshall, S Univ Strathclyde Dept Elect & Elect Engn Glasgow G1 1XW Lanark Scotland

Mathematical morphology is the analysis of signals and images in terms of shape. Much is based on simple positive boolean functions that are used to produce filters for binary and greyscale signals and images, In a recent development, the standard operators are applied to connected sets that form maxima and minima. These are new, powerful, general tools for analysing and representing images.

关键词： Digital signal processing shape digital filters image representation signal representation connected sets binary signals greyscale images boolean functions mathematical morphology image processing binary images greyscale signals Formal logic Optical information, image and video signal processing signal processing Computer vision and image processing techniques mathematical positive boolean functions representation Signal processing and detection filters

来源：评论

学校读者我要写书评

暂无评论

DECOMPOSITIONS OF positive SELF-DUAL boolean functions

引用

DISCRETE MATHEMATICS 1995年第1-3期140卷 23-46页

作者： BIOCH, JC IBARAKI, T ERASMUS UNIV ROTTERDAM DEPT COMP SCIAI SECT3000 DR ROTTERDAMNETHERLANDS KYOTO UNIV FAC ENGNDEPT APPL MATH & PHYSKYOTO 606JAPAN

A coterie, which is used to realize mutual exclusion in distributed systems, is a family C of subsets such that any pair of subsets in C has at least one element in common, and such that no subset in C contains any other subset in C. Associate with a family of subsets C a positive boolean function f(c) such that f(c)(x) = 1 if the boolean vector x is equal to or greater than the characteristic vector of some subset in C, and 0 otherwise. It is known that C is a coterie if and only if f(c) is dual-minor, and is a non-dominated (ND) coterie if and only if f(c) is self-dual. We study in this paper the decomposition of a positive self-dual function into smaller positive self-dual functions, as it explains how to represent and how to construct the corresponding ND coterie. A key step is how to decompose a positive dual-minor function f into a conjunction of positive self-dual functions f(1),f(2),...,f(k). In addition to the general condition for this decomposition, we clarify the condition for the decomposition into two functions f(1) and f(2), and introduce the concept of canonical decomposition. Then we present an algorithm that determines a minimal canonical decomposition, and a very simple algorithm that usually gives a decomposition close to minimal. The decomposition of a general self-dual function is also discussed.

关键词： MUTUAL EXCLUSION COTERIES positive boolean functions MONOTONE boolean functions SELF-DUAL functions DUAL-MINOR functions DECOMPOSITION OF SELF-DUAL functions

来源：评论

学校读者我要写书评

暂无评论

WEIGHTED MEDIANS - positive boolean functions CONVERSION ALGORITHMS

引用

SIGNAL PROCESSING 1993年第2期34卷 149-161页

作者： NIEWEGLOWSKI, J GABBOUJ, M NEUVO, Y Department of Electrical Engineering Tampere University of Technology P.O. Box 553 SF-33101 Tampere Finland

Weighted Medians with integer weights are widely used nonlinear operators in signal processing. Weighted median filters belong to the class of stack filters. Since each stack filter is uniquely specified by its corresponding positive boolean function, the latter can be used to analyze the behavior of the filter. On the other hand, weighted medians are usually represented by a given set of weights. In this paper, weighted medians are first extended to include weighted median operators with positive real-valued weights. It is shown that any real weighted median is equivalent to an integer weighted median. As a consequence, a sensitivity analysis can always be performed to represent real weighted medians by finite precision weighted medians. This result proves very useful if one realizes that optimal adaptive weighted medians are usually real-valued. Conversion algorithms are presented to find the positive boolean function representing a given weighted median and a set of weights of a weighted median representing a given positive boolean function if feasible.

关键词： WEIGHTED MEDIAN positive boolean functions STACK FILTERS NONLINEAR FILTERING

来源：评论

学校读者我要写书评

暂无评论

GENERATING AND APPROXIMATING NONDOMINATED COTERIES

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1995年第9期6卷 905-914页

作者： BIOCH, JC IBARAKI, T KYOTO UNIV FAC ENGNDEPT APPL MATH & PHYSKYOTO 606JAPAN

A coterie, which is used to realize mutual exclusion in a distributed system, is a family C of incomparable subsets such that every pair of subsets in C has at least one element in common, Associate with a family of subsets C a positive (i,e., monotone) boolean function f(C) such that f(C)(x) = 1 if the boolean vector x is equal to or greater than the characteristic vector of some subset in C, and 0 otherwise, It is known that C is a coterie if and only if f(C) is dual-minor, and is a nondominated (ND) coterie if and only if f(C) is self-dual. In this paper, we introduce an operator rho, which transforms a positive self-dual function into another positive self-dual function, and the concept of almost-self-duality, which is a close approximation to self-duality and can be checked in polynomial time (the complexity of checking positive self-duality is currently unknown), After proving several interesting properties of them, we propose a simple algorithm to check whether a given positive function is self-dual or not, Although this is not a polynomial algorithm, it is practically efficient in most cases, Finally, we present an incrementally polynomial algorithm that generates all positive self-dual functions (ND coteries) by repeatedly applying rho operations, Based on this algorithm, all ND coteries of up to seven variables are computed.

关键词： ALMOST-SELF-DUAL functions COTERIES DUALIZATION MONOTONE boolean functions MUTUAL-EXCLUSION NONDOMINATED COTERIES positive boolean functions SELF-DUAL functions

来源：评论

学校读者我要写书评

暂无评论

STACKING MATRIX BASED FAST PROCEDURE FOR OPTIMAL STACK FILTER DESIGN 5

STACKING MATRIX BASED FAST PROCEDURE FOR OPTIMAL STACK FILTE...

引用

Conference on Image Algebra and Morphological Image Processing V

作者： TABUS, I GABBOUJ, M TAMPERE UNIV TECHNOL SIGNAL PROC LABSF-33101 TAMPEREFINLAND

ISBN: (纸本)081941624X

Given a set of cost coefficients, obtained from a "representative" training data set and some desired set, we have previously shown that the optimal boolean filter, based on a defined error criterion, is obtained by simple compare/assign operations. If, on the other hand, the desired solution is a stack filter, three steps must be added to the above procedure. Following the compare/assign step above, we check if the resulting solution is of the desired type. If not, we compute the maximal positive boolean function contained in the resulting boolean function. Finally, we check if adding other minterms to the positive boolean function obtained in the previous step will improve the criterion value. The first step requires a very low computational effort. For the following three steps, matrix based procedures using the stacking matrix, are derived. First, we derive a fast procedure for checking the positivity of a boolean function. This procedure can be written in a single line using Matlab® language. The following step consists of finding the maximal positive boolean function embedded in a given boolean function. Again, a fast procedure is derived for this task, which can also be written in one line using Matlab® language. The final step checks for improvement, in the cost criterion, when adding other minterms to the positive boolean function, resulting from the previous step. We will use again the stacking matrix to accomplish this task, resulting in a three-line Matlab®code. Some examples are provided to illustrate each step in the above procedure.

关键词： STACKING MATRIX OPTIMAL STACK FILTER DESIGN positive boolean functions

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：