Search results for "boolean"
showing 10 items of 98 documents
Analysis of Spatially and Temporally Overlapping Events with Application to Image Sequences
2006
Counting spatially and temporally overlapping events in image sequences and estimating their shape-size and duration features are important issues in some applications. We propose a stochastic model, a particular case of the nonisotropic 3D Boolean model, for performing this analysis: the temporal Boolean model. Some probabilistic properties are derived and a methodology for parameter estimation from time-lapse image sequences is proposed using an explicit treatment of the temporal dimension. We estimate the mean number of germs per unit area and time, the mean grain size and the duration distribution. A wide simulation study in order to assess the proposed estimators showed promising resul…
Exacus: Efficient and Exact Algorithms for Curves and Surfaces
2005
We present the first release of the Exacus C++ libraries. We aim for systematic support of non-linear geometry in software libraries. Our goals are efficiency, correctness, completeness, clarity of the design, modularity, flexibility, and ease of use. We present the generic design and structure of the libraries, which currently compute arrangements of curves and curve segments of low algebraic degree, and boolean operations on polygons bounded by such segments.
Pseudocomplements in sum-ordered partial semirings
2007
We study a particular way of introducing pseudocomplementation in ordered semigroups with zero, and characterise the class of those pseudocomplemented semigroups, termed g-semigroups here, that admit a Glivenko type theorem (the pseudocomplements form a Boolean algebra). Some further results are obtained for g-semirings – those sum-ordered partially additive semirings whose multiplicative part is a g-semigroup. In particular, we introduce the notion of a partial Stone semiring and show that several well-known elementary characteristics of Stone algebras have analogues for such semirings.
The expressive power of the shuffle product
2010
International audience; There is an increasing interest in the shuffle product on formal languages, mainly because it is a standard tool for modeling process algebras. It still remains a mysterious operation on regular languages.Antonio Restivo proposed as a challenge to characterize the smallest class of languages containing the singletons and closed under Boolean operations, product and shuffle. This problem is still widely open, but we present some partial results on it. We also study some other smaller classes, including the smallest class containing the languages composed of a single word of length 2 which is closed under Boolean operations and shuffle by a letter (resp. shuffle by a l…
Transience versus recurrence for scale-free spatial networks
2020
Weight-dependent random connection graphs are a class of local network models that combine scale-free degree distribution, small-world properties and clustering. In this paper we discuss recurrence or transience of these graphs, features that are relevant for the performance of search and information diffusion algorithms on the network.
Tighter Relations between Sensitivity and Other Complexity Measures
2014
The sensitivity conjecture of Nisan and Szegedy [12] asks whether the maximum sensitivity of a Boolean function is polynomially related to the other major complexity measures of Boolean functions. Despite major advances in analysis of Boolean functions in the past decade, the problem remains wide open with no positive result toward the conjecture since the work of Kenyon and Kutin from 2004 [11].
Boolean Functions of Low Polynomial Degree for Quantum Query Complexity Theory
2007
The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. This is why Boolean functions are needed with a high number of essential variables and a low polynomial degree. Unfortunately, it is a well-known problem to construct such functions. The best separation between these two complexity measures of a Boolean function was exhibited by Ambai- nis [5]. He constructed functions with polynomial degree M and number of variables Omega(M2). We improve such a separation to become exponenti…
Quantum Query Complexity of Boolean Functions with Small On-Sets
2008
The main objective of this paper is to show that the quantum query complexity Q(f) of an N-bit Boolean function f is bounded by a function of a simple and natural parameter, i.e., M = |{x|f(x) = 1}| or the size of f's on-set. We prove that: (i) For $poly(N)\le M\le 2^{N^d}$ for some constant 0 < d < 1, the upper bound of Q(f) is $O(\sqrt{N\log M / \log N})$. This bound is tight, namely there is a Boolean function f such that $Q(f) = \Omega(\sqrt{N\log M / \log N})$. (ii) For the same range of M, the (also tight) lower bound of Q(f) is $\Omega(\sqrt{N})$. (iii) The average value of Q(f) is bounded from above and below by $Q(f) = O(\log M +\sqrt{N})$ and $Q(f) = \Omega (\log M/\log N+ \sqrt{N…
Complexity of decision trees for boolean functions
2004
For every positive integer k we present an example of a Boolean function f/sub k/ of n = (/sub k//sup 2k/) + 2k variables, an optimal deterministic tree T/sub k/' for f/sub k/ of complexity 2k + 1 as well as a nondeterministic decision tree T/sub k/ computing f/sub k/. with complexity k + 2; thus of complexity about 1/2 of the optimal deterministic decision tree. Certain leaves of T/sub k/ are called priority leaves. For every input a /spl isin/ {0, 1}/sup n/ if any of the parallel computation reaches a priority leaves then its label is f/sub k/ (a). If the priority leaves are not reached at all then the label on any of the remaining leaves reached by the computation is f/sub k/. (a).
Quantum Queries on Permutations with a Promise
2009
This paper studies quantum query complexities for deciding (exactly or with probability 1.0) the parity of permutations of n numbers, 0 through n *** 1. Our results show quantum mechanism is quite strong for this non-Boolean problem as it is for several Boolean problems: (i) For n = 3, we need a single query in the quantum case whereas we obviously need two queries deterministically. (ii) For even n , n /2 quantum queries are sufficient whereas we need n *** 1 queries deterministically. (iii) Our third result is for the problem deciding whether the given permutation is the identical one. For this problem, we show that there is a nontrivial promise such that if we impose that promise to the …