Search results for "boolean"
showing 10 items of 98 documents
The fluted fragment revisited
2019
AbstractWe study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, motivated by the work of W. V. Quine. We show that the satisfiability problem for this fragment has nonelementary complexity, thus refuting an earlier published claim by W. C. Purdy that it is in NExpTime. More precisely, we consider ${\cal F}{{\cal L}^m}$, the intersection of the fluted fragment and the m-variable fragment of first-order logic, for all $m \ge 1$. We show that, for $m \ge 2$, this subfragment forces $\left\lfloor {m/2} \right\rfloor$-tuply exponentially large models, and that its satisfiability problem is $\left\lfloor {m/2} \right\rfloor$-NExpTime-hard. We…
Team Theory and Person-by-Person Optimization with Binary Decisions
2012
In this paper, we extend the notion of person-by-person (pbp) optimization to binary decision spaces. The novelty of our approach is the adaptation to a dynamic team context of notions borrowed from the pseudo-boolean optimization field as completely local-global or unimodal functions and submodularity. We also generalize the concept of pbp optimization to the case where groups of $m$ decisions makers make joint decisions sequentially, which we refer to as $m$b$m$ optimization. The main contribution is a description of sufficient conditions, verifiable in polynomial time, under which a pbp or an $m$b$m$ optimization algorithm converges to the team-optimum. As a second contribution, we prese…
Equivalence Relations on Stonian Spaces
1996
Abstract Quotient spaces of locally compact Stonian spaces which generalize in some sense the concept of Stone representation space of a Boolean algebra are investigated emphasizing the measure theoretical point of view, and a representation theorem for finitely additive measures is proved.
BMaD – A Boolean Matrix Decomposition Framework
2014
Boolean matrix decomposition is a method to obtain a compressed representation of a matrix with Boolean entries. We present a modular framework that unifies several Boolean matrix decomposition algorithms, and provide methods to evaluate their performance. The main advantages of the framework are its modular approach and hence the flexible combination of the steps of a Boolean matrix decomposition and the capability of handling missing values. The framework is licensed under the GPLv3 and can be downloaded freely at http://projects.informatik.uni-mainz.de/bmad.
Boolean operations mediated by an ion-pair receptor of a multi-readout molecular logic gate
2013
A heteroditopic BODIPY dye that performs all basic Boolean operations with a cation (K+) and an anion (F-) as inputs and absorption, transmission and fluorescence as outputs is described. The molecular logic gate can also act as a digital comparator between the inputs.
Multi-label classification using boolean matrix decomposition
2012
This paper introduces a new multi-label classifier based on Boolean matrix decomposition. Boolean matrix decomposition is used to extract, from the full label matrix, latent labels representing useful Boolean combinations of the original labels. Base level models predict latent labels, which are subsequently transformed into the actual labels by Boolean matrix multiplication with the second matrix from the decomposition. The new method is tested on six publicly available datasets with varying numbers of labels. The experimental evaluation shows that the new method works particularly well on datasets with a large number of labels and strong dependencies among them.
Integration of an LP Solver into Interval Constraint Propagation
2011
This paper describes the integration of an LP solver into iSAT, a Satisfiability Modulo Theories solver that can solve Boolean combinations of linear and nonlinear constraints. iSAT is a tight integration of the well-known DPLL algorithm and interval constraint propagation allowing it to reason about linear and nonlinear constraints. As interval arithmetic is known to be less efficient on solving linear programs, we will demonstrate how the integration of an LP solver can improve the overall solving performance of iSAT.
Generalized person-by-person optimization in team problems with binary decisions
2008
In this paper, we extend the notion of person by person optimization to binary decision spaces. The novelty of our approach is the adaptation to a dynamic team context of notions borrowed from the pseudo-boolean optimization field as completely local-global or unimodal functions and sub- modularity. We also generalize the concept of pbp optimization to the case where the decision makers (DMs) make decisions sequentially in groups of m, we call it mbm optimization. The main contribution are certain sufficient conditions, verifiable in polynomial time, under which a pbp or an mbm optimization algorithm leads to the team-optimum. We also show that there exists a subclass of sub-modular team pr…
Studying endocytosis in space and time by means of temporal Boolean models
2006
Endocytosis is a process by which cells carry traffic from the extracellular space into various intracellular compartments. Visualization of fluorescently tagged clathrin proteins (mediators of endocytosis) allows us to image endocytosis in real time. When imaging the plasma membrane, areas of fluorescence generated by different endocytic processes overlap spatially and temporally, forming random clumps. Here, a sequence of segmented clathrin spots is considered a realization of a non-isotropic 3D Boolean model. Estimates of the intensity, the mean perimeter and the density function of the durations of endocytic events are obtained.
Quantum Query Algorithms for Conjunctions
2010
Every Boolean function can be presented as a logical formula in conjunctive normal form. Fast algorithm for conjunction plays significant role in overall algorithm for computing arbitrary Boolean function. First, we present a quantum query algorithm for conjunction of two bits. Our algorithm uses one quantum query and correct result is obtained with a probability p = 4/5, that improves the previous result. Then, we present the main result - generalization of our approach to design efficient quantum algorithms for computing conjunction of two Boolean functions. Finally, we demonstrate another kind of an algorithm for conjunction of two bits, that has a correct answer probability p = 9/10. Th…