613 research outputs found
Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to Online Indexing
No full textThis paper presents a general technique for optimally transforming any dynamic data structure that operates on atomic and indivisible keys by constant-time comparisons, into a data structure that handles unbounded-length keys whose comparison cost is not a constant. Examples of these keys are strings, multidimensional points, multiple-precision numbers, multikey data (e.g., records), XML paths, URL addresses, etc. The technique is more general than what has been done in previous work as no particular exploitation of the underlying structure is required. The only requirement is that the insertion of a key must identify its predecessor or its successor. Using the proposed technique, online suffix tree construction can be done in worst case time per input symbol (as opposed to amortized time per symbol, achieved by previously known algorithms). To our knowledge, our algorithm is the first that achieves worst case time per input symbol. Searching for a pattern of length in the resulting suffix tree takes time, where is the number of occurrences of the pattern. The paper also describes more applications and shows how to obtain alternative methods for dealing with suffix sorting, dynamic lowest common ancestors, and order maintenance. The technical features of the proposed technique for a given data structure are the following ones. The new data structure is obtained from by augmenting the latter with an oracle for strings, extending the functionalities of the Dietz--Sleator list for order maintenance [P. F. Dietz and D. D. Sleator, Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, ACM, New York, 1987, pp. 365--372; A. Tsakalidis, Acta Inform., 21 (1984), pp. 101--112]. The space complexity of is memory cells for storing keys, where denotes the space complexity of . Then, each operation involving keys taken from requires time, where denotes the time complexity of the corresponding operation originally supported in . Each operation involving a key not stored in takes time, where denotes the length of . For the special case where the oracle handles suffixes of a string, the achieved insertion time is
Front Matter, Table of Contents, Preface
No full textFront Matter, Table of Contents, Preface, List of Author
When Science Meets the Public: Proceedings of a Workshop Organized by the American Association for the Advancement of Science, Committee on Public Understanding of Science and Technology, February 17, 1991, Washington, DC
No full textProceedings of a workshop on "When Science Meets the Public," held at annual conference of American Association for the Advancement of Science, Washington, DC, 17 February 1991. Contributions from: Sheila Grinnell; Bruce V. Lewenstein; Philip Morrison; John Ziman; Valerie Crane; Marcel C. LaFollette; Brian Wynne; Kara L. Marchman and Janine Jason; Eve R. Hall, Shalom M. Fisch, and Edward T. Esty; Sharon Dunwoody; Jonathan Ward; Libby Palmer; Tom Siegfried; Robert Sullivan; Katherine E. Rowan; Shirley M. Malcom; Patricia S. CurlinCommittee on Public Understanding of Science & Technology (COPUST) of the American Association for the Advancement of Science (AAAS
Fractional quantum Hall states of a Bose gas with a spin-orbit coupling
No full textWe study the fractional quantum Hall phases of a pseudospin-1/2 Bose gas in an artificial gauge field. In addition to an external magnetic field, the gauge field mimics an intrinsic spin-orbit coupling of the Rashba type. While the spin degeneracy of the Landau levels is lifted by the spin-orbit coupling, the crossing of two Landau levels at certain coupling strengths gives rise to a new degeneracy. We therefore take into account two Landau levels and perform exact diagonalization of the many-body Hamiltonian. We study and characterize the quantum Hall phases which occur in the vicinity of the degeneracy point. Notably, we describe the different states appearing at the Laughlin fillings,nu = 1/2 and nu = 1/4. While for these filling factors incompressible phases disappear at the degeneracy point, we find gaps in the spectra of denser systems at nu = 3/2 and nu = 2. For filling factors nu = 2/3 and nu = 4/3, we discuss the connection of the exact ground states to the non-Abelian spin singlet states, obtained as the ground states of (k + 1)-body contact interactions
Parameterized matching with mismatches
No full textThe problem of approximate parameterized string searching consists of ¯nding, for a
given text t = t1t2:::tn and pattern p = p1p2:::pm over respective alphabets §t and §p,
the injection ¼i from §p to §t maximizing the number of matches between ¼i(p) and
titi+1:::ti+m¡1 (i = 1; 2; :::n¡m+1). We examine the special case where both strings are
run-length encoded, and further restrict to the case where one of the alphabets is binary.
For this case, we give a construction working in time O(n + (rp £ rt) ®(rt) log(rt)),
where rp and rt denote the number of runs in the corresponding encodings for y and x,
respectively, and ® is the inverse of the Ackermann's function
On structural physical approximations and entanglement breaking maps
No full textVery recently, a conjecture saying that the so-called structural physical approximations (SPAs) to optimal positive maps (optimal entanglement witnesses) give entanglement breaking (EB) maps (separable states) has been posed (Korbicz et al 2008 Phys. Rev. A 78 062105). The main purpose of this contribution is to explore this subject. First, we extend the set of entanglement witnesses supporting the conjecture. Then, we ask whether SPAs constructed from other than the depolarizing channel maps also lead to EB maps and show that in general this is not the case. On the other hand, we prove an interesting fact that for any positive map Lambda, there exists an EB channel Phi such that the SPA of Lambda constructed with the aid of Phi is again an EB channel. Finally, we ask similar questions in the case of continuous variable systems. We provide a simple way of constructing SPA and prove that in the case of the transposition map it gives the EB channel.
Topological characterization of chiral models through their long time dynamics
No full textWe study chiral models in one spatial dimension, both static and periodically driven. We demonstrate that their topological properties may be read out through the long time limit of a bulk observable, the mean chiral displacement. The derivation of this result is done in terms of spectral projectors, allowing for a detailed understanding of the physics. We show that the proposed detection converges rapidly and it can be implemented in a wide class of chiral systems. Furthermore, it can measure arbitrary winding numbers and topological boundaries, it applies to all non-interacting systems, independently of their quantum statistics, and it requires no additional elements, such as external fields, nor filled bands
Space-Efficient String Indexing for Wildcard Pattern Matching
No full textIn this paper we describe compressed indexes that support pattern matching queries for strings with wildcards. For a constant size alphabet our data structure uses O(n.log^e(n)) bits for any e>0 and reports all occ occurrences of a wildcard string in O(m+s^g.M(n)+occ) time, where M(n)=o(log(log(log(n)))), s is the alphabet size, m is the number of alphabet symbols and g is the number of wildcard symbols in the query string. We also present an O(n)-bit index with O((m+s^g+occ).log^e(n)) query time and an O(n{log(log(n))}^2)-bit index with O((m+s^g+occ).log(log(n))) query time. These are the first non-trivial data structures for this problem that need o(n.log(n)) bits of space
Haake-Lewenstein-Wilkens approach to spin-glasses revisited
No full textWe revisit the Haake-Lewenstein-Wilkens (HLW) approach to Edwards-Anderson
(EA) model of Ising spin glass [Phys. Rev. Lett. 55, 2606 (1985)]. This
approach consists in evaluation and analysis of the probability distribution of
configurations of two replicas of the system, averaged over quenched disorder.
This probability distribution generates squares of thermal copies of spin
variables from the two copies of the systems, averaged over disorder, that is
the terms that enter the standard definition of the original EA order
parameter, qEA. We use saddle point/steepest descent method to calculate the
average of the Gaussian disorder in higher dimensions. This approximate result
suggest that qEA >0 at 0 <T <Tc in 3D and 4D. The case of 2D seems to be a
little more subtle, since in the present approach energy increase for a domain
wall competes with boundary/edge effects more strongly in 2D; still our
approach predicts spin glass order at sufficiently low temperature. We
speculate, how these predictions confirm/contradict widely spread opinions
that: i) There exist only one (up to the spin flip) ground state in EA model in
2D, 3D and 4D; ii) There is (no) spin glass transition in 3D and 4D (2D). This
paper is dedicated to the memories of Fritz Haake and Marek Cieplak.Comment: 10 pages, 8 figure
- …
