Motivated by mass-spectrometry protein sequencing, we consider the problem of
reconstructing a string from the multisets of its substring composition. We show that all …

A 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 …

The Binary Jumbled String Matching Problem is defined as follows: Given a string s over {a,
b} of length n and a query (x, y), with x, y non-negative integers, decide whether s has a …

A prefix normal word is a binary word with the property that no substring has more 1s than
the prefix of the same length. This class of words is important in the context of binary jumbled …

Given a simple graph G with n vertices and a natural number i≤ n, let LG (i) be the
maximum number of leaves that can be realized by an induced subtree T of G with i vertices …

The asymptotic number of prefix normal words - ScienceDirect Skip to main contentSkip to
article Elsevier logo Journals & Books Search RegisterSign in View PDF Download full issue …

An abelian antipower of order k (or simply an abelian k-antipower) is a concatenation of k
consecutive words of the same length having pairwise distinct Parikh vectors. This definition …

Prefix normal words are binary words in which each prefix has at least the same number of 1
s as any factor of the same length. Firstly introduced in 2011, the problem of determining the …

We present a new recursive generation algorithm for prefix normal words. These are binary
words with the property that no factor has more 1s than the prefix of the same length. The …

Prefix normal words are binary words that have no factor with more 1s than the prefix of the
same length. Finite prefix normal words were introduced in [Fici and Lipták, DLT 2011]. In …