17,653 research outputs found
Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
No full textA prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. By proving that the set of prefix normal words is a bubble language, we can exhaustively list all prefix normal words of length n as a combinatorial Gray code, where successive strings differ by at most two swaps or bit flips. This Gray code can be generated in O(log2n) amortized time per word, while the best generation algorithm hitherto has O(n) running time per word. We also present a membership tester for prefix normal words, as well as a novel characterization of bubble languages
ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS
No full textBurcsi P, Cicalese F, Fici G, Lipták Z. ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS. International Journal of Foundations of Computer Science. 2012;23(02):357-374.The Parikh vector p(s) of a string s over a finite ordered alphabet Sigma = {a(1), . . . , a(sigma)} is defined as the vector of multiplicities of the characters, p(s) = (p(1), . . . , p(sigma)), where p(i) = vertical bar{j vertical bar s(j) = a(i)}vertical bar. Parikh vector q occurs in s if s has a substring t with p(t) = q. The problem of searching for a query q in a text s of length n can be solved simply and worst-case optimally with a sliding window approach in O(n) time. We present two novel algorithms for the case where the text is fixed and many queries arrive over time. The first algorithm only decides whether a given Parikh vector appears in a binary text. It uses a linear size data structure and decides each query in O(1) time. The preprocessing can be done trivially in Theta(n(2)) time. The second algorithm finds all occurrences of a given Parikh vector in a text over an arbitrary alphabet of size sigma >= 2 and has sub-linear expected time complexity. More precisely, we present two variants of the algorithm, both using an O(n) size data structure, each of which can be constructed in O(n) time. The first solution is very simple and easy to implement and leads to an expected query time of O(n(sigma/log sigma)(1/2) log m/root m), where m = Sigma(i) q(i) is the length of a string with Parikh vector q. The second uses wavelet trees and improves the expected runtime to O(n(sigma/log sigma)(1/2) 1 root m), i.e., by a factor of log m
A Method for Evaluating the Quality of String Dissimilarity Measures and Clustering Algorithms for EST Clustering.
No full textZimmermann J, Lipták Z, Hazelhurst S. A Method for Evaluating the Quality of String Dissimilarity Measures and Clustering Algorithms for EST Clustering. In: Proc. BIBE. 2004: 301-309
Review of the book How Fascism Works, by J. Stanley
No full textDr. Devin Z. Shaw (Douglas College) reviews the book How fascism works, by J. Stanley (2020).Final article published
Novel Results on the Number of Runs of the Burrows-Wheeler-Transform
No full textThe Burrows-Wheeler-Transform (BWT), a reversible string transformation, is one of the fundamental components of many current data structures in string processing. It is central in data compression, as well as in efficient query algorithms for sequence data, such as webpages, genomic and other biological sequences, or indeed any textual data. The BWT lends itself well to compression because its number of equal-letter-runs (usually referred to as r) is often considerably lower than that of the original string; in particular, it is well suited for strings with many repeated factors. In fact, much attention has been paid to the r parameter as measure of repetitiveness, especially to evaluate the performance in terms of both space and time of compressed indexing data structures. In this paper, we investigate ρ(v), the ratio of r and of the number of runs of the BWT of the reverse of v. Kempa and Kociumaka [FOCS 2020] gave the first non-trivial upper bound as ρ(v) = O(log 2(n) ), for any string v of length n. However, nothing is known about the tightness of this upper bound. We present infinite families of binary strings for which ρ(v) = Θ(log n) holds, thus giving the first non-trivial lower bound on ρ(n), the maximum over all strings of length n. Our results suggest that r is not an ideal measure of the repetitiveness of the string, since the number of repeated factors is invariant between the string and its reverse. We believe that there is a more intricate relationship between the number of runs of the BWT and the string’s combinatorial properties
Evidence for the decay B0→J/ψω and measurement of the relative branching fractions of meson decays to J/ψη and J/ψη′
No full textFirst evidence of the B 0 → J / ψ ω decay is found and the B s 0 → J / ψ η and B s 0 → J / ψ η ′ decays are studied using a dataset corresponding to an integrated luminosity of 1.0 fb -1 collected by the LHCb experiment in proton-proton collisions at a centre-of-mass energy of sqrt(s) = 7 TeV. The branching fractions of these decays are measured relative to that of the B 0 → J / ψ ρ 0 decay:frac(B (B 0 → J / ψ ω), B (B 0 → J / ψ ρ 0)) = 0.89 ± 0.19 (stat) - 0.13 + 0.07 (syst),frac(B (B s 0 → J / ψ η), B (B 0 → J / ψ ρ 0)) = 14.0 ± 1.2 (stat) - 1.5 + 1.1 (syst) - 1.0 + 1.1 (frac(f d, f s)),frac(B (B s 0 → J / ψ η ′), B (B 0 → J / ψ ρ 0)) = 12.7 ± 1.1 (stat) - 1.3 + 0.5 (syst) - 0.9 + 1.0 (frac(f d, f s)), where the last uncertainty is due to the knowledge of f d / f s, the ratio of b-quark hadronization factors that accounts for the different production rate of B 0 and B s 0 mesons. The ratio of the branching fractions of B s 0 → J / ψ η ′ and B s 0 → J / ψ η decays is measured to befrac(B (B s 0 → J / ψ η ′), B (B s 0 → J / ψ η)) = 0.90 ± 0.09 (stat) - 0.02 + 0.06 (syst)
On prefix normal words and prefix normal forms
No full textA 1-prefix normal word is a binary word with the property that no factor has more 1s than the prefix of the same length; a 0-prefix normal word is defined analogously. These words arise in the context of indexed binary jumbled pattern matching, where the aim is to decide whether a word has a factor with a given number of 1s and 0s (a given Parikh vector). Each binary word has an associated set of Parikh vectors of the factors of the word. Using prefix normal words, we provide a characterization of the equivalence class of binary words having the same set of Parikh vectors of their factors. We prove that the language of prefix normal words is not context-free and is strictly contained in the language of pre-necklaces, which are prefixes of powers of Lyndon words. We give enumeration results on pnw(n), the number of prefix normal words of length n, showing that, for sufficiently large n, 2n−4nlgn≤pnw(n)≤2n−lgn+1. For fixed density (number of 1s), we show that the ordinary generating function of the number of prefix normal words of length n and density d is a rational function. Finally, we give experimental results on pnw(n), discuss further properties, and state open problem
Lyman break galaxies and the star formation rate of the Universe at z ~ 6
No full textWe determine the space density of UV-luminous starburst galaxies at z≈ 6 using deep HST ACS SDSS-i′ (F775W) and SDSS-z′ (F850LP) and VLT ISAAC J and Ks band imaging of the Chandra Deep Field South. We find eight galaxies and one star with (i′−z′) > 1.5 to a depth of z′AB= 25.6 (an 8σ detection in each of the 3 available ACS epochs). This corresponds to an unobscured star formation rate of ≈15 h−270 M⊙ yr−1 at z= 5.9, equivalent to L* for the Lyman-break population at z= 3–4 (ΩΛ= 0.7, ΩM= 0.3). We are sensitive to star-forming galaxies at 5.6 ≲z≲ 7.0 with an effective comoving volume of ≈1.8 × 105h−370 Mpc3 after accounting for incompleteness at the higher redshifts due to luminosity bias. This volume should encompass the primeval subgalactic-scale fragments of the progenitors of about a thousand L* galaxies at the current epoch. We determine a volume-averaged global star formation rate of (6.7 ± 2.7) × 10−4h70 M⊙ yr−1 Mpc−3 at z∼ 6 from rest-frame UV selected starbursts at the bright end of the luminosity function: this is a lower limit because of dust obscuration and galaxies below our sensitivity limit. This measurement shows that at z∼ 6 the star formation density at the bright end is a factor of ∼6 times less than that determined by Steidel et al. for a comparable sample of UV-selected galaxies at z= 3–4, and so extends our knowledge of the star formation history of the Universe to earlier times than previous work and into the epoch where reionization may have occurred
Measurement of the ratio of prompt χ c to J / ψ production in pp collisions at √s = 7 TeV
No full textThe prompt production of charmonium χ c and J / ψ states is studied in proton-proton collisions at a centre-of-mass energy of √s = 7 TeV at the Large Hadron Collider. The χ c and J / ψ mesons are identified through their decays χ c → J / ψ γ and J / ψ → μ + μ - using 36 pb - 1 of data collected by the LHCb detector in 2010. The ratio of the prompt production cross-sections for χ c and J / ψ, σ (χ c → J / ψ γ) / σ (J / ψ), is determined as a function of the J / ψ transverse momentum in the range 2 < p T J / ψ < 15 GeV / c. The results are in excellent agreement with next-to-leading order non-relativistic expectations and show a significant discrepancy compared with the colour singlet model prediction at leading order, especially in the low p T J / ψ region
Measurement of the branching fraction
No full textThe B
0
s
→ J/ψK
0
S
branching fraction is measured in a data sample corresponding to 0.41 fb−1
of integrated luminosity collected with the LHCb detector at the LHC. This channel is sensitive to
the penguin contributions affecting the sin 2β measurement from B
0
→ J/ψK
0
S
. The time-integrated
branching fraction is measured to be B(B
0
s
→ J/ψK
0
S
) = (1.83±0.28)×10−5
. This is the most precise
measurement to date
- …
