The problem called "String reconstruction from substrings" is a mathematical model of sequencing by hybridization that plays an important role in DNA sequencing. In this problem, we are given a blackbox oracle holding an unknown string ${\mathcal X}$ and are required to obtain (reconstruct) ${\mathcal X}$ through "substring queries" $Q(S)$. $Q(S)$ is given to the oracle with a string $S$ and the answer of the oracle is Yes if ${\mathcal X}$ includes $S$ as a substring and No otherwise. Our goal is to minimize the number of queries for the reconstruction. In this paper, we deal with only binary strings for ${\mathcal X}$ whose length $n$ is given in advance by using a sequence of good $S$'s. In 1995, Skiena and Sundaram first studied this problem and obtained an algorithm whose query complexity is $n+O(\log n)$. Its information theoretic lower bound is $n$, and they posed an obvious open question; if we can remove the $O(\log n)$ additive term. No progress has been made until now. This paper gives two partially positive answers to this open question. One is a randomized algorithm whose query complexity is $n+O(1)$ with high probability and the other is an average-case algorithm also having a query complexity of $n+O(1)$ on average. The $n$ lower bound is still true for both cases, and hence they are optimal up to an additive constant.

A word is quasiperiodic (or coverable) if it can be covered with occurrences of another finite word, called its quasiperiod. A word is multi-scale quasiperiodic (or multi-scale coverable) if it has infinitely many different quasiperiods. These notions were previously studied in the domains of text algorithms and combinatorics of right infinite words. We extend them to infinite pictures (two-dimensional words). Then we compare the regularity properties (uniform recurrence, uniform frequencies, topological entropy) of quasiperiodicity with multi-scale quasiperiodicity, and we also compare each of them with its one-dimensional counterpart. We also study which properties of quasiperiods enforce properties on the quasiperiodic words.

A word is quasiperiodic if it can be obtained by concatenations and overlaps of a smaller word, called a quasiperiod. Based on links between quasiperiods, right special factors and square factors, we introduce a method to determine the set of quasiperiods of a given right infinite word. Then we study the structure of the sets of quasiperiods of right infinite words and, using our method, we provide examples of right infinite words with extremal sets of quasiperiods (no quasiperiod is quasiperiodic, all quasiperiods except one are quasiperiodic, ...). Our method is also used to provide a short proof of a recent characterization of quasiperiods of the Fibonacci word. Finally we extend this result to a new characterization of standard Sturmian words using a property of their sets of quasiperiods.