Search results for "rete"
showing 10 items of 3470 documents
An Exact Algorithm for the Quadratic Assignment Problem on a Tree
1989
The Tree QAP is a special case of the Quadratic Assignment Problem (QAP) where the nonzero flows form a tree. No condition is required for the distance matrix. This problem is NP-complete and is also a generalization of the Traveling Salesman Problem. In this paper, we present a branch-and-bound algorithm for the exact solution of the Tree QAP based on an integer programming formulation of the problem. The bounds are computed using a Lagrangian relaxation of this formulation. To solve the relaxed problem, we present a Dynamic Programming algorithm which is polynomially bounded. The obtained lower bound is very sharp and equals the optimum in many cases. This fact allows us to employ a redu…
Error-Free Affine, Unitary, and Probabilistic OBDDs
2018
We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results for the automata versions of these models.
A simple algorithm for generating neuronal dendritic trees
1990
Abstract A simple, efficient algorithm is presented for generating the codewords of all neuronal dendritic trees with a given number of terminal nodes. Furthermore, a procedure is developed for deciding if different codewords correspond to topologically equivalent trees.
Periodic and Chaotic Orbits of a Neuron Model
2015
In this paper we study a class of difference equations which describes a discrete version of a single neuron model. We consider a generalization of the original McCulloch-Pitts model that has two thresholds. Periodic orbits are investigated accordingly to the different range of parameters. For some parameters sufficient conditions for periodic orbits of arbitrary periods have been obtained. We conclude that there exist values of parameters such that the function in the model has chaotic orbits. Models with chaotic orbits are not predictable in long-term.
Schaefer–Krasnoselskii fixed point theorems using a usual measure of weak noncompactness
2012
Abstract We present some extension of a well-known fixed point theorem due to Burton and Kirk [T.A. Burton, C. Kirk, A fixed point theorem of Krasnoselskii–Schaefer type, Math. Nachr. 189 (1998) 423–431] for the sum of two nonlinear operators one of them compact and the other one a strict contraction. The novelty of our results is that the involved operators need not to be weakly continuous. Finally, an example is given to illustrate our results.
Quantum walks on two-dimensional grids with multiple marked locations
2015
The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration (the placement and the number) of marked locations. While the first dependence has been studied in a number of papers, the second dependence remains mostly unstudied.We study search by quantum walks on the two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [3]. The original paper analyses one and two marked locations only. We move beyond two marked locations and study the behaviour of the algorithm for several configurations of multiple marked locations.In this paper, we prove two results showing the importance of how the marked locations ar…
Improved constructions of quantum automata
2008
We present a simple construction of quantum automata which achieve an exponential advantage over classical finite automata. Our automata use \frac{4}{\epsilon} \log 2p + O(1) states to recognize a language that requires p states classically. The construction is both substantially simpler and achieves a better constant in the front of \log p than the previously known construction of Ambainis and Freivalds (quant-ph/9802062). Similarly to Ambainis and Freivalds, our construction is by a probabilistic argument. We consider the possibility to derandomize it and present some results in this direction.
Spatial Search on Grids with Minimum Memory
2015
We study quantum algorithms for spatial search on finite dimensional grids. Patel et al. and Falk have proposed algorithms based on a quantum walk without a coin, with different operators applied at even and odd steps. Until now, such algorithms have been studied only using numerical simulations. In this paper, we present the first rigorous analysis for an algorithm of this type, showing that the optimal number of steps is $O(\sqrt{N\log N})$ and the success probability is $O(1/\log N)$, where $N$ is the number of vertices. This matches the performance achieved by algorithms that use other forms of quantum walks.
Symmetry-assisted adversaries for quantum state generation
2011
We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem. This problem encompasses both, the computation of partial or total functions and the preparation of target quantum states. There has been hope for quite some time that quantum state generation might be a route to tackle the $backslash$sc Graph Isomorphism problem. We show that for the related problem of $backslash$sc Index Erasure our method leads to a lower bound of $backslash Omega(backslash sqrt N)$ which matches an upper bound obtained via reduction to quantum search on $N$ elements. This closes an open problem first raised by Shi [FOCS'02]. Our approach is …
Exceptional Quantum Walk Search on the Cycle
2016
Quantum walks are standard tools for searching graphs for marked vertices, and they often yield quadratic speedups over a classical random walk's hitting time. In some exceptional cases, however, the system only evolves by sign flips, staying in a uniform probability distribution for all time. We prove that the one-dimensional periodic lattice or cycle with any arrangement of marked vertices is such an exceptional configuration. Using this discovery, we construct a search problem where the quantum walk's random sampling yields an arbitrary speedup in query complexity over the classical random walk's hitting time. In this context, however, the mixing time to prepare the initial uniform state…