Exact Transversal Hypergraphs and Application to Boolean μ-Functions

Call an hypergraph, that is a family of subsets (edges) from a finite vertex set, an exact transversal hypergraph iff each of its minimal transversals, i.e., minimal vertex subsets that intersect each edge, meets each edge in a singleton. We show that such hypergraphs are recognizable in polynomial time and that their minimal transversals as well as their maximal independent sets can be generated in lexicographic order with polynomial delay between subsequent outputs, which is impossible in the general case unless P= NP. The results obtained are applied to monotone Boolean μ-functions, that are Boolean functions defined by a monotone Boolean expression (that is, built with ∧, ∨ only) in which no variable occurs repeatedly. We also show that recognizing such functions from monotone Boolean expressions is co-NP-hard, thus complementing Mundici's result that this problem is in co-NP.     

Dualization of boolean functions using ternary decision diagrams

Dualization of Boolean functions is a fundamental problem that appears in various fields such as artificial intelligence, logic, data mining, etc. For monotone Boolean functions, many empirical researches that focus on practical efficiency have recently been done. We extend our previous work for monotone dualization and present a novel method for dualization that allows us to handle any Boolean function, including non-monotone Boolean functions. We furthermore present a variant of this method in cooperation with all solutions solver. By experiments we evaluate efficiency and characteristics of our methods.     

Partially defined computer instructions and guards

We here extend our earlier work on the theory of computer instructions to consider instructions which are only partially defined. For every such instruction, we assume that it is defined whenever a certain Boolean expression is true; we refer to such a Boolean expression as a guard, following Dijkstra. This is a special case of a more general function on the set of states of a computer, representing an expression in a programming language. Many constructs for instructions now generalize to partially defined instructions; in particular, we define the notion of conditional input and output regions, as well as the relevant region of a more general expression. Fundamental theorems about instructions generalize to theorems about guards and about partially defined instructions. We also define the parallel execution of such instructions, which is useful in validating a generalized instruction commutativity criterion.     

Almost-measurability relation induced by lattice-valued partial possibilistic measures

Possibilitic measures are set functions which can be taken into consideration as a mathematical tool for uncertainty quantification and processing, alternative to standard probability measures. For a number of practical reasons and restrictions, worth a more detailed investigating are partial possibilistic measures with non-numerical values, e.g. with values in partially ordered sets (POS) in general or in complete lattices in particular. For non-measurable sets, i.e. for the sets outside the domain of the partial possibilistic measure in question, we define their inner and outer measure, applying the basic idea of classical measure theory and approximating these sets, in the best possible way, by their measurable subsets and coverings. Inspired by the notion of symmetric difference, we introduce a lattice-valued metric or distance function and define a set to be almost measurable, if the distance between the value of its inner and outer measure is below a "small" lattice-valued threshold values, so generalizing the idea of measurability in the Lebesgue sense from the standard measure theory. A number of results dealing with the notion of lattice-valued almost-measurability and with the classes of almost measurable sets are stated and proved.     

Recognition of interval Boolean functions

Interval functions constitute a special class of Boolean functions for which it is very easy and fast to determine their functional value on a specified input vector. The value of an n-variable interval function specified by interval [a,b] (where a and b are n-bit binary numbers) is true if and only if the input vector viewed as an n-bit number belongs to the interval [a,b]. In this paper we study the problem of deciding whether a given disjunctive normal form represents an interval function and if so then we also want to output the corresponding interval. For general Boolean functions this problem is co-NP-hard. In our article we present a polynomial time algorithm which works for monotone functions. We shall also show that given a Boolean function f belonging to some class which is closed under partial assignment and for which we are able to solve the satisfiability problem in polynomial time, we can also decide whether f is an interval function in polynomial time. We show how to recognize a “renamable” variant of interval functions, i.e., their variable complementation closure. Another studied problem is the problem of finding an interval extension of partially defined Boolean functions. We also study some other properties of interval functions.      

Decision lists and related Boolean functions

We consider Boolean functions represented by decision lists, and study their relationships to other classes of Boolean functions. It turns out that the elementary class of 1-decision lists has interesting relationships to independently defined classes such as disguised Horn functions, read-once functions, nested differences of concepts, threshold functions, and 2-monotonic functions. In particular, 1-decision lists coincide with fragments of the mentioned classes. We further investigate the recognition problem for this class, as well as the extension problem in the context of partially defined Boolean functions (pdBfs). We show that finding an extension of a given pdBf in the class of 1-decision lists is possible in linear time. This improves on previous results. Moreover, we present an algorithm for enumerating all such extensions with polynomial delay.     

On learning monotone Boolean functions under the uniform distribution

In this paper, we prove two general theorems on monotone Boolean functions which are useful for constructing a learning algorithm for monotone Boolean functions under the uniform distribution.     

A 4n-lower bound on the monotone network complexity of a one-output boolean function

The main purpose of Boolean network theory is to find functions f:{0, 1}ⁿ → {0, 1} with large network complexity. The best known lower bound over the complete basis of all binary functions is of size 3n for a non-monotone function (Blum (1982)). Bloniarz (1979) has proved a 3n-lower bound for the majority-function over the monotone basis. In this paper a special function is presented for which a lower bound of size 4n over the monotone basis can be proved.     

Limiting negations in bounded-depth circuits: An extension of Markov's theorem

A theorem of Markov shows the necessary and sufficient number of negations for computing an arbitrary collection of Boolean functions. In this paper, we consider a class of bounded-depth circuits, in which each gate computes an arbitrary monotone Boolean function or its negation. We show tight bounds on the number of negations for computing an arbitrary collection of Boolean functions when such a class of circuits is under consideration.     

Cross-Correlation Analysis of Cryptographically Useful Boolean Functions and S-Boxes

We use the cross-correlation function as a fundamental tool to study cryptographic properties of Boolean functions. This provides a unified treatment of a large section of Boolean function literature. In the process we generalize old results and obtain new characterizations of cryptographic properties. In particular, new characterizations of bent functions and functions satisfying propagation characteristics are obtained in terms of the cross-correlation and auto-correlation properties of subfunctions. The exact relationship between the algebraic structure of the non-zeros of the spectrum and the auto-correlation values is obtained for a cryptographically important class of functions. Finally we study the suitability of S-boxes in stream ciphers and conclude that currently known constructions for S-boxes may not be adequate for such applications. Received April 27, 2001, and in revised form October 30, 2001. Online publication February 20, 2002.     

A fuzzy set based solution method for multiobjective optimal design problem of mechanical and structural systems using functional-link net

The principle of solving multiobjective optimization problems with fuzzy sets theory is studied. Membership function is the key to introduce the fuzzy sets theory to multiobjective optimization. However, it is difficult to determine membership functions in engineering applications. On the basis of rapid quadratic optimization in the learning of weights, simplification in hardware as well as in computational procedures of functional-link net, discrete membership functions are used as sample training data. When the network converges, the continuous membership functions implemented with the network. Membership functions based on functional-link net have been used in multiobjective optimization. An example is given to illustrate the method.     

Function S-rough sets and law identification

By introducing element equivalence class that proposes dynamic characteristic into Pawlak Z rough sets theory, the first author of this paper improved Pawlak Z rough sets and put forward S-rough sets （singular rough sets）. S-rough sets are defined by element equivalence class that proposes dynamic characteristic. S-rough sets have dynamic characteristic. By introducing the function equivalence class （law equivalence class） that proposes dynamic characteristic into S-rough sets, the first author improved S-rough sets and put forward function S-rough sets （function singular rough sets）. Function S-rough sets have dynamic characteristic and law characteristic, and a function is a law. By using function S-rough sets, this paper presents law identification, law identification theorem, and law identification criterion and applications. Function S-rough sets are a new research direction of rough sets theory, and it is also a new tool to the research of system law identification.     

一般多状态单调关联系统

多状态单调关联系统是系统可靠性理论的新发展,目前见到的研究均在元件(系统)状态集 合为全序集条件下进行的.这种结构实际应用有一定的局限性.本文根据实际系统的单调性 状,在元件与系统状态集合为偏序的假定下,给出一类多状态单调关联系统的定义.并对其结 构性质、随机性质及分布类封闭性质进行了研究,得出若干结果.     

多粒度支持直觉模糊粗糙集的多属性决策方法

针对多属性决策中多个相互冲突的属性信息使决策者很难做出决策判断的问题,文中从支持直觉模糊集的角度研究该问题.首先,在支持直觉模糊集的基础上,结合多粒度粗糙集理论,构造乐观、悲观两种多粒度支持直觉模糊粗糙集模型,分析两种模型之间的相互关系,讨论相关性质.然后,利用t-模和t-余模定义拟合函数,提出多粒度支持直觉模糊粗糙集的多属性决策求解方法,同时定义得分函数和精确函数排序决策结果,提取相应的决策规则,设计算法.实例分析表明,文中方法使决策者在处理信息冲突的多属性决策问题时可根据实际需求选择最优决策方案     

The algebraic structures of generalized rough set theory

Rough set theory is an important technique for knowledge discovery in databases, and its algebraic structure is part of the foundation of rough set theory. In this paper, we present the structures of the lower and upper approximations based on arbitrary binary relations. Some existing results concerning the interpretation of belief functions in rough set backgrounds are also extended. Based on the concepts of definable sets in rough set theory, two important Boolean subalgebras in the generalized rough sets are investigated. An algorithm to compute atoms for these two Boolean algebras is presented.     

关于二型模糊集合的一些基本问题

采用集合论的方法给出了单位模糊集合和二型模糊集合及其在一点的限制等定义,使得二型模糊集合更易于理解.通过定义嵌入单位模糊集合来描述一般二型模糊集合,并给出离散、半连通二型模糊集合的表达式.根据论域、主隶属度及隶属函数的特性将二型模糊集合分为四种类型:离散、半连通、连通及复合型,并根据连通的特点将连通二型模糊集合分为单连通及多连通两类.利用支集的闭包（Closure of support,CoS）划分法表述主隶属度及区间二型模糊集合.提出了CoS二、三次划分法分别来表述单、复连通二型模糊集合,并使每一个子区域的上下边界及次隶属函数在该子区域上的限制分别具有相同的解析表述式.最后,探讨了二型模糊集合在一点的限制、主隶属度、支集、嵌入单位模糊集合之间的关系.     

On the equal-weight symmetric Boolean functions

Two important classes of symmetric Boolean functions are the equal-weight Boolean functions and the elementary (or homogeneous) symmetric Boolean functions. In this paper we studied the equal-weight symmetric Boolean functions. First the Walsh spectra of the equal-weight symmetric Boolean functions are given. Second the sufficient and necessary condition on correlation-immunity of the equal-weight symmetric Boolean function is derived and other cryptology properties such as the nonlinearity, balance and propagation criterion are taken into account. In particular, the nonlinearity of the equal-weight symmetric Boolean functions with n (n ≥ 10) variables is determined by their Hamming weight. Considering these properties will be helpful in further investigations of symmetric Boolean functions.     

Two algorithms for generating structured and unstructured monotone ordinal data sets

Monotone constraints are very common while dealing with multi-attribute ordinal problems. Grinding wheels hardness selection, timely replacements of costly laser sensors in silicon wafer manufacturing, and the selection of the right personnel for sensitive production facilities, are just a few examples of ordinal problems where monotonicity makes sense.In order to evaluate the performance of various ordinal classifiers one needs both artificially generated as well as real world data sets. Two algorithms are presented for generating monotone ordinal data sets. The first can be used for generating random monotone ordinal data sets without an underlying structure. The second algorithm, which is the main contribution of this paper, describes for the first time how structured monotone data sets can be generated.     

Boolean functions with long prime implicants

In this short note we introduce a hierarchy of classes of Boolean functions, where each class is defined by the minimum allowed length of prime implicants of the functions in the class. We show that for a given DNF and a given class in the hierarchy, it is possible to test in polynomial time whether the DNF represents a function from the given class. For the first class in the hierarchy we moreover present a polynomial time algorithm which for a given input DNF outputs a shortest logically equivalent DNF, i.e. a shortest DNF representation of the underlying function. This class is therefore a new member of a relatively small family of classes for which the Boolean minimization problem can be solved in polynomial time. For the second class and higher classes in the hierarchy we show that the Boolean minimization problem can be approximated within a constant factor.     

The complexity of monotone boolean functions

We study the realization of monotone Boolean functions by networks. Our main result is a precise version of the following statement: the complexity of realizing a monotone Boolean function ofn arguments is less by the factor (2/n)^1/2, where is the circular ratio, than the complexity of realizing an arbitrary Boolean function ofn arguments. The proof combines known results concerning monotone Boolean functions with new methods relating the computing abilities of networks and machines.