共查询到20条相似文献,搜索用时 15 毫秒
1.
Jan C. Bioch 《Annals of Mathematics and Artificial Intelligence》1998,24(1-4):69-91
Many data-analysis algorithms in machine learning, datamining and a variety of other disciplines essentially operate on discrete
multi-attribute data sets. By means of discretisation or binarization also numerical data sets can be successfully analysed.
Therefore, in this paper we view/introduce the theory of (partially defined) discrete functions as an important theoretical
tool for the analysis of multi-attribute data sets. In particular we study monotone (partially defined) discrete functions.
Compared with the theory of Boolean functions relatively little is known about (partially defined) monotone discrete functions.
It appears that decision lists are useful for the representation of monotone discrete functions. Since dualization is an important
tool in the theory of (monotone) Boolean functions, we study the interpretation and properties of the dual of a (monotone)
binary or discrete function. We also introduce the dual of a pseudo-Boolean function. The results are used to investigate
extensions of partially defined monotone discrete functions and the identification of monotone discrete functions. In particular,
we present a polynomial time algorithm for the identification of so-called stable discrete functions.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
2.
Ana Gàl 《Computational Complexity》2001,10(4):277-296
We give a characterization of span program size by a
combinatorial-algebraic measure. The measure we consider is a generalization
of a measure on covers which has been used to prove lower
bounds on formula size and has also been studied with respect to communication
complexity.?In the monotone case our new methods yield lower bounds for
the monotone span program complexity of explicit Boolean functions in
n variables over arbitrary fields, improving the previous lower bounds
on monotone span program size. Our characterization of span program
size implies that any matrix with superpolynomial separation between
its rank and cover number can be used to obtain superpolynomial lower
bounds on monotone span program size. We also identify a property
of bipartite graphs that is suficient for constructing Boolean functions
with large monotone span program complexity.
Received: September 30, 2000. 相似文献
3.
《Journal of Symbolic Computation》1994,17(3):215-225
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. 相似文献
4.
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. 相似文献
5.
V. M. Blinovsky 《Problems of Information Transmission》2014,50(3):280-284
We prove two correlation inequalities conjectured in [1] for functions that are linear combinations of unimodal Boolean monotone nondecreasing functions. 相似文献
6.
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. 相似文献
7.
Ingo Wegener 《Theoretical computer science》1979,9(1):147-150
Schnorr[1] proved a lower bound on the number of additions in monotone computations of rational polynomials. He conjectured a similar lower bound on the number of ∨-gates in monotone networks computing monotone Boolean functions. We disprove this conjecture. 相似文献
8.
Several results on the monotone circuit complexity and the conjunctive complexity, i.e., the minimal number of AND gates in
monotone circuits, of quadratic Boolean functions are proved. We focus on the comparison between single level circuits, which
have only one level of AND gates, and arbitrary monotone circuits, and show that there is an exponential gap between the conjunctive
complexity of single level circuits and that of general monotone circuits for some explicit quadratic function. Nearly tight
upper bounds on the largest gap between the single level conjunctive complexity and the general conjunctive complexity over
all quadratic functions are also proved. Moreover, we describe the way of lower bounding
the single level circuit complexity and give a set of quadratic functions whose monotone complexity is strictly smaller than
its single level complexity. 相似文献
9.
Nicholas Pippenger 《Theory of Computing Systems》1977,11(1):289-316
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. 相似文献
10.
Ondřej Čepek David Kronus Petr Kučera 《Annals of Mathematics and Artificial Intelligence》2008,52(1):1-24
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.
相似文献
11.
Ingo Wegener 《Acta Informatica》1980,13(2):109-114
Summary Neciporuk [3], Lamagna/Savage [1] and Tarjan [6] determined the monotone network complexity of a set of Boolean sums if each two sums have at most one variable in common. By this result they could define explicitely a set of n Boolean sums which depend on n variables and whose monotone complexity is of order n
3/2. In the main theorem of this paper we prove a more general lower bound on the monotone network complexity of Boolean sums. Our lower bound is for many Boolean sums the first nontrivial lower bound. On the other side we can prove that the best lower bound which the main theorem yields is the n
3/2-bound cited above. For the proof we use the technical trick of assuming that certain functions are given for free. 相似文献
12.
The two important qualities of a cipher are security and speed. Frequently, to satisfy the security of a Boolean function primitive, speed may be traded-off. In this paper, we present a general construction that addresses both qualities. The idea of our construction is to manipulate a cryptographically strong base function and one of its affine equivalent functions, using concatenation and negation. We achieve security from the inherent qualities of the base function, which are preserved (or increased), and obtain speed by the simple Boolean operations. We present two applications of the construction to demonstrate the flexibility and efficiency of the construction. 相似文献
13.
Erik D. Demaine Martin L. Demaine Yair N. Minsky Joseph S. B. Mitchell Ronald L. Rivest Mihai Pǎtraşcu 《Theory of Computing Systems》2014,54(4):531-550
We show how to hang a picture by wrapping rope around n nails, making a polynomial number of twists, such that the picture falls whenever any k out of the n nails get removed, and the picture remains hanging when fewer than k nails get removed. This construction makes for some fun mathematical magic performances. More generally, we characterize the possible Boolean functions characterizing when the picture falls in terms of which nails get removed as all monotone Boolean functions. This construction requires an exponential number of twists in the worst case, but exponential complexity is almost always necessary for general functions. 相似文献
14.
We explore the revenue capabilities of truthful, monotone (“fair”) allocation and pricing functions for resource-constrained
auction mechanisms within a general framework that encompasses unlimited supply auctions, knapsack auctions, and auctions
with general non-decreasing convex production cost functions. We study and compare the revenue obtainable in each fair pricing
scheme to the profit obtained by the ideal omniscient multi-price auction. We show that for capacitated knapsack auctions,
no constant pricing scheme can achieve any approximation to the optimal profit, but proportional pricing is as powerful as
general monotone pricing. In addition, for auction settings with arbitrary bounded non-decreasing convex production cost functions,
we present a proportional pricing mechanism which achieves a poly-logarithmic approximation. Unlike existing approaches, all
of our mechanisms have fair (monotone) prices, and all of our competitive analysis is with respect to the optimal profit extraction. 相似文献
15.
Nicholas Pippenger 《Theoretical computer science》1980,11(1):49-56
In his paper “On a Boolean matrix”, Nechiporuk gave an explicit example of a set of n homogeneous monotone Boolean functions of the first degree in n variables that require Ω(n3/2) two-input gates in any monotone Boolean network computing them. In this note we show how this can be extended to Ω(n5/3) two-input gates. 相似文献
16.
The problem of maximum depth of monotone Boolean functions is investigated when k-input AND and OR gates are used for realisation. 相似文献
17.
P. N. Bibilo 《Automation and Remote Control》2014,75(7):1173-1194
We propose a decomposition method for systems of incompletely specified Boolean functions represented as binary decision diagrams. Minimizing the number of intermediate functions in such a decomposition is intended to improve the performance of Boolean circuits made of library elements. A characteristic feature of our method is the fact that after decomposition (cutting) of the original binary decision diagram one of two decomposition units is represented as a system of DNFs. 相似文献
18.
Linear multi-secret sharing schemes 总被引:2,自引:0,他引:2
XIAO Liangliang & LIU Mulan Academy of Mathematics System Sciences Key Laboratory of Mathematics Mechanization Chinese Academy of Sciences Beijing China 《中国科学F辑(英文版)》2005,48(1):125-136
In this paper the linear multi-secret sharing schemes are studied by using monotone span programs. A relation between computing monotone Boolean functions by using monotone span programs and realizing multi-access structures by using linear multi-secret sharing schemes is shown. Furthermore, the concept of optimal linear multi-secret sharing scheme is presented and the several schemes are proved to be optimal. 相似文献
19.
We consider the problem of dualizing a Boolean function f given by CNF, i.e., computing a CNF for its dual fd. While this problem is not solvable in quasi-polynomial total time in general (unless SAT is solvable in quasi-polynomial time), it is so in case the input belongs to special classes, e.g., the class of bidual Horn CNF ? [Discrete Appl. Math. 96-97 (1999) 55-88] (i.e., both ? and its dual ?d represent Horn functions). In this paper, we show that a disguised bidual Horn CNF ? (i.e., ? becomes a bidual Horn CNF after renaming of variables) can be recognized in polynomial time, and its dualization can be done in quasi-polynomial total time. We also establish a similar result for dualization of prime CNFs. 相似文献
20.
Tomá? Kroupa 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2012,16(11):1851-1861
We generalise belief functions to many-valued events which are represented by elements of Lindenbaum algebra of infinite-valued ?ukasiewicz propositional logic. Our approach is based on mass assignments used in the Dempster–Shafer theory of evidence. A generalised belief function is totally monotone and it has Choquet integral representation with respect to a unique belief measure on Boolean events. 相似文献