i\leqslant k$. Then each $y_{i}^{\prime}$ is a nonnegative integer. The
general conclusion follows from the first part. ∎

We now conclude from Equation 15 and Lemma VII.4 that
$\left|\mathcal{I}^{(t)}\right|=\binom{\frac{n}{2}-t+1-l}{l}$ and thus the
size of $S^{(t)}$ is

$\displaystyle\left|S^{(t)}\right|$
$\displaystyle=\sum_{l=3}^{\frac{n}{2}-t+1}2^{\frac{n}{2}-l-1}\binom{\frac{n}{2}-t+1-l}{l}M_{l+1}+2^{\frac{n}{2}-1}+\left(\frac{n}{2}-t\right)2^{\frac{n}{2}-2}+2\binom{n/2-t-1}{2}2^{\frac{n}{2}-3}$
$\displaystyle=\sum_{l=0}^{\frac{n}{2}-t+1}2^{\frac{n}{2}-l-1}\binom{\frac{n}{2}-t+1-l}{l}M_{l+1},$
(16)

where the binomial coefficient $\binom{a}{b}$ is define to be $0$ if $a<b$,
and the term $M_{l+1}$ follows from the fact that $s_{1}s_{i_{1}}\cdots
s_{i_{l}}$ is a Catlan-Bertrand string for each $\mathbf{s}\in S^{(t)}$.

###### Corollary VII.5

Let $t\geqslant 2$ be a fixed integer and $n>2t+8$, then the size of
$\mathcal{C}_{A}^{(t)}$ is

$\sum_{i=0}^{\frac{n}{2}-t}\binom{\frac{n}{2}-t}{i}2^{\frac{n}{2}-t-i}M_{i}+\sum_{l=0}^{\frac{n}{2}-t+1}2^{\frac{n}{2}-l-1}\binom{\frac{n}{2}-t+1-l}{l}M_{l+1}.$

###### Proof:

Notice that
$\left|\mathcal{C}_{A}^{(t)}\right|=\left|S^{(t)}\right|+\left|\mathcal{S}_{R}^{(t)}(n)\right|$.
Then the conclusion follows from Equation 14 and Section VII. ∎

Recall that $M_{l+1}=\binom{l}{\frac{l}{2}}$ if $l$ is even and
$M_{l+1}=\frac{1}{2}\binom{l+1}{\frac{l+1}{2}}$ if $l$ is odd. Proposition 1
in [18] implies

$\displaystyle\frac{2^{\frac{n}{2}-1}}{\sqrt{\pi\left(\left\lfloor\frac{n+3}{4}-\frac{t}{2}\right\rfloor+1\right)}}\sum_{l=0}^{\frac{n}{2}-t+1}\binom{\frac{n}{2}-t+1-l}{l}\leqslant\left|S^{(t)}\right|\leqslant\frac{2^{\frac{n}{2}-1}}{\sqrt{\pi/2}}\sum_{l=0}^{\frac{n}{2}-t+1}\binom{\frac{n}{2}-t+1-l}{l}$
(17)

To further estimate the order of magnitude of $\left|S^{(t)}\right|$, we need
the following lemma.

###### Lemma VII.6

For any nonnegative integer $m$, we have

$L_{m}\triangleq\sum_{k=0}^{m}\binom{m-k}{k}=F_{m+1},$

where $F_{m+1}=\frac{(1+\sqrt{5})^{m+1}-(1-\sqrt{5})^{m+1}}{2^{m+1}\sqrt{5}}$
is the $(m+1)$th Fibonacci number.

###### Proof:

Notice that $\binom{m-k}{k}=\binom{m-k-1}{k}+\binom{m-k-1}{k-1}$ when
$k\geqslant 1$ and $m\geqslant k$. So when $m\geqslant 2$, we have

$\displaystyle L_{m}$
$\displaystyle=1+\sum_{k=1}^{m}\binom{m-k}{k}=1+\sum_{k=1}^{\left\lfloor\frac{m}{2}\right\rfloor}\binom{m-k}{k}$
$\displaystyle=1+\sum_{k=1}^{\left\lfloor\frac{m}{2}\right\rfloor}\binom{m-k-1}{k}+\sum_{k=1}^{\left\lfloor\frac{m}{2}\right\rfloor}\binom{m-k-1}{k-1}$
$\displaystyle=\sum_{k=0}^{\left\lfloor\frac{m}{2}\right\rfloor}\binom{m-1-k}{k}+\sum_{k=0}^{\left\lfloor\frac{m}{2}\right\rfloor-1}\binom{m-2-k}{k}$
$\displaystyle=\sum_{k=0}^{m-1}\binom{m-1-k}{k}+\sum_{k=0}^{m-2}\binom{m-2-k}{k}=L_{m-1}+L_{m-2}.$

This implies that $L_{m}$ satisfies the recurrence relation of Fibonacci
numbers. On the other hand, $L_{0}=1=F_{1}$ and $L_{1}=2=F_{2}$. Therefore,
$L_{m}=F_{m+1}$ for all $m\geqslant 0$. ∎

###### Corollary VII.7

The lower bound of $\left|S^{(t)}\right|$ is
$\Omega\left(\frac{(2\alpha)^{\frac{n}{2}}}{\sqrt{n}}\right)$, and the upper
bound of $\left|S^{(t)}\right|$ is $O\left((2\alpha)^{\frac{n}{2}}\right)$, ,
where $\alpha=\frac{1+\sqrt{5}}{2}$.

###### Proof:

Theorem 8.1 in [25] asserts that
$F_{m+1}=\left\lfloor\frac{\alpha^{m+1}}{\sqrt{5}}+\frac{1}{2}\right\rfloor$
for all $m\geqslant 0$. Then the conclusion follows from Equation 17 and Lemma
VII.6. ∎

Since $\alpha\approx 1.618<2$, Equation 14 and Corollary VII.7 imply that the
order of magnitude of $\left|S^{(t)}\right|$ is strictly smaller than that of
$\left|\mathcal{S}_{R}^{(t)}(n)\right|$. However, since $\alpha$ is relatively
close to $2$, we still add many strings into $\mathcal{S}_{R}^{(t)}(n)$ to
obtain $\mathcal{C}_{A}^{(t)}$.

##  VIII $r$-Length Limited Composition Multiset

In this section we suggest a new reconstruction model. Recall that in order to
store data, two molecules with different mass are synthesized to represent the
0 and 1 symbols. These molecules are combined into a string to represent the
data that the user wishes to store. In order to read the data, the synthetic
polymers are read by tandem mass (MS/MS) spectrometer. As part of the reading
process, the polymer molecule breaks in a position which is chosen at random,
creating a prefix and a suffix. The breaking of the molecule is usually made
by collisions, bombardment of the molecule with electrons or photons, or a
chemical reaction (a molecule can also break down due to instability). It is
reasonable to assume that longer molecule fragments tend to break more often
than shorter fragments. For example, using electron bombardment, it is more
likely that the electron will hit a longer polymer fragment than hitting a
short fragment. As a result, when the mass readings of the fragments are
obtained, the composition of long fragments will not appear in those readings.
Leaving us with a composition multiset of shorter strings.

Since our results in this section apply to general alphabets, we assume our
alphabet is a $q$-ary alphabet $\Sigma_{q}=\\{a_{i}~{}:~{}a_{i}=i,0\leqslant
i\leqslant q-1\\}$, where $q\geqslant 2$ is an integer. Let $\Sigma_{q}^{*}$
denote the set of all strings over $\Sigma_{q}$ of finite length. For a string
$\mathbf{s}\in\Sigma_{q}^{*}$, we define the composition $c(\mathbf{s})$ of
$\mathbf{s}$ to be $c(\mathbf{s})=a_{0}^{d_{0}}a_{1}^{d_{1}}\cdots
a_{q-1}^{d_{q-1}}$, where $d_{i}$ is the number of appearances of the symbol
$a_{i}$ in $\mathbf{s}$ and we omit $a_{i}^{d_{i}}$ if $d_{i}=0$. For example,
let $\Sigma=\left\\{0,1,2\right\\}$, $\mathbf{s}=001112$ and
$\mathbf{t}=02002$, then $c(\mathbf{s})=0^{2}1^{3}2^{1}$ and
$c(\mathbf{t})=0^{3}2^{2}$. For a length-$n$ string $\mathbf{s}$ and an
integer $1\leqslant l\leqslant n$, the notation $C_{l}(\mathbf{s})$ can be
similarly defined as in Section VII.

To model the phenomenon described as above, dubbed the $r$-length limited
composition multiset model, we assume that the composition multiset does not
contain the composition of substrings longer than $r$. The mathematical model
is defined next.

###### Definition VIII.1

For a string $\mathbf{s}\in\Sigma_{q}^{n}$ and for a positive integer
$r\leqslant n$, we denote by $C_{\leqslant r}(\mathbf{s})$ the multiset of
compositions of all substrings of length at most $r$ in $\mathbf{s}$, i.e.,

$C_{\leqslant r}(\mathbf{s})=\bigcup_{i=1}^{r}C_{i}(\mathbf{s}).$

In this section we initiate the study of $r$-length limited composition
multiset model, and present a simple coding scheme for the case where $r=r(n)$
is a linear function of the length of the strings $n$. To that end, we define
the following relation on strings. For $\mathbf{u},\bm{v}\in\Sigma_{q}^{n}$,
we say that $\mathbf{u},\bm{v}$ are cyclic-equivalent, denoted
$\mathbf{u}\overset{c}{\sim}\bm{v}$, if $\mathbf{u}$ is a cyclic shift of
$\bm{v}$. It is immediate that $\overset{c}{\sim}$ is an equivalence relation.
A string $\mathbf{u}$ is called minimal if it is the minimal (with respect to
the lexicographic order) string among all its equivalent strings. A string
$\mathbf{u}\in\Sigma_{2}^{n}$ is called periodic if there exists a string
$\bm{v}$ such that $\mathbf{u}=\bm{v}^{t}$ with $t\geqslant 2$, where
$\bm{v}^{t}$ denotes the consecutive concatenation of $\bm{v}$ with itself $t$
times. A string is called aperiodic if it is not periodic.

###### Definition VIII.2

A string $\mathbf{w}\in\Sigma_{q}^{*}$ is called a Lyndon string if
$\mathbf{w}$ is minimal and aperiodic. We denote by $\mathcal{L}_{r}(q)$ the
set of all Lyndon words of length $r$ over $\Sigma_{q}$.

Lyndon words were first introduced in [26, 27] and were used to study free
abelian groups. They have been found useful in various topics such as
differential equations, cryptography, and coding theory [28, 29, 30].

For a Lyndon word $\mathbf{l}\in\mathcal{L}_{r}(q)$, denote by $m$ the maximal
number of consecutive $a_{q}$ symbols that appear at the end of $\mathbf{l}$,
i.e., $\mathbf{l}=l_{1}l_{2}\dots l_{r-m}a_{q}^{m}$ where $m\geqslant 0$ is
maximal and $l_{r-m}<a_{q}$. We construct our code $\mathcal{C}_{r}$ as
follows

$\mathcal{C}_{r}=\left\\{\mathbf{l}a_{q}^{r-m}~{}:~{}\mathbf{l}\in\mathcal{L}_{r}(q)\right\\}.$

So a codeword $\mathbf{s}\in\mathcal{C}_{r}$ is a Lyndon string of length $r$
followed by a string of repeated $a_{q}$ such that $\mathbf{s}$ ends with $r$
consecutive $a_{q}$ symbols. The strings in $\mathcal{C}_{r}$ have variable
length. The shortest codeword has $r+1$ symbols (obtained by Lyndon words of
the form $a_{i}a_{q}^{r-1}$ for $i<q-1$, and then
$\mathbf{s}=a_{i}a_{q}^{r}$), and the longest codeword has $2r$ symbols if
$q>2$ and $2r-1$ symbols if the alphabet contains two symbols (obtained by the
Lyndon words $a_{i}\dots a_{i}a_{j}$ with $i<j<q$, concatenated with
$a_{q}^{r}$ to generate $\mathbf{s}=a_{i}^{r-1}a_{j}a_{q}^{r}$). If length-$n$
codewords are in need, where $n\geqslant 2r$, such a set $\mathcal{C}_{r}(n)$
can be obtained by padding every codeword in $\mathcal{C}_{r}$ with $a_{q}$
until it reaches length $n$.

The main goal of this section is to prove the following corollary which will
be readily obtained from the discussion in this section.

###### Corollary VIII.3

Let $\Sigma_{q}$ be an alphabet of size $q$ and consider the $r$-length
limited composition multiset model with a fixed $r$. Every codeword
$\mathbf{s}\in\mathcal{C}_{r}$ is uniquely reconstructible given $C_{\leqslant
r}(\mathbf{s})$ and the code rate is

$R=\frac{\log_{q}\left(|\mathcal{C}_{r}|\right)}{\text{Avg. length of
}\mathbf{s}\in\mathcal{C}_{r}}\geqslant\frac{1}{2}\left(1+o(1)\right).$

In order to generate the set $\mathcal{L}_{r}(q)$ we can use the efficient
algorithm given in [31, 32] for finding Lyndon words of length at most $r$,
according to their lexicographic order. The algorithm is presented here for
completeness.

Algorithm 1 Algorithm that generates next Lyndon words (up to length $r$)

1:A Lyndon word $\mathbf{w}\in\Sigma_{q}^{*}$.

2:The next Lyndon word $\mathbf{u}$ according to the lexicographic order.

3:Let $\mathbf{s}=(\mathbf{w}^{r})_{1}^{r}$, i.e., concatenate $\mathbf{w}$ to
itself to form a string $\mathbf{s}\in\Sigma_{q}^{r}$ with
$\mathbf{s}_{i}=\mathbf{w}_{i\bmod|\mathbf{w}|}$.

4:while last symbol of $\mathbf{s}$ is the maximal symbol in lexicographic
order do

5: Remove the last symbol from $\mathbf{s}$, i.e.,
$\mathbf{s}=\mathbf{s}_{1}^{|\mathbf{s}|-1}$.

6:end while

7:Replace the last symbol in $\mathbf{s}$ by its successor according to the
Lexicographic order to generate $\mathbf{u}$.

8:Return $\mathbf{u}$

###### Example VIII.4

Let $\Sigma_{q}=\left\\{0,1,2,3\right\\}$ with the usual ordering and let
$\mathbf{w}=003103$ be a Lyndon word of length $|\mathbf{w}|=6$. Applying
Algorithm 1 with $r=9$ we first generate $\mathbf{s}=003103003$. Next, we
eliminate the last symbol since it is the maximal symbol in our alphabet, to
obtain $\mathbf{s}=00310300$. Lastly, we replace the last symbol $0$ with its
successor $1$ to obtain $\mathbf{u}=00310301$.

Notice that the algorithm may also provide a string which is shorter than $r$.
Consider the Lyndon word $\mathbf{w}=00000333$. Eliminating the maximal symbol
in Step 3 of the algorithm yields $\mathbf{s}=000000$ (as the output at Step
4) and the next Lyndon word obtained is $\mathbf{u}=000001$ which is of length
$6$.

Instead of showing that every codeword $\mathbf{s}\in\mathcal{C}_{r}$ can be
uniquely reconstructed from $C_{\leqslant r}(\mathbf{s})$, we show that
$\mathbf{s}$ can be uniquely reconstructed from the multiset
$C_{r}(\mathbf{s})$ of compositions of substring of length $r$. Indeed, notice
that there are no Lyndon words of length $r$ with $r$ appearances of $a_{q}$.
This implies that $a_{q}^{r}$ appears exactly once in $C_{r}(\mathbf{s})$.
From that point onward, we can construct $\mathbf{s}$ backwards by considering
compositions containing a decreasing number of $a_{q}$s.

The number of length-$r$ Lyndon words over an alphabet $\Sigma_{q}$ is given
by Witt’s formula [33]

$|\mathcal{L}_{r}(q)|=\frac{1}{r}\sum_{d|r}\mu(d)q^{r/d}$

where $\mu$ is the Möebius function.

Since $\mu(\cdot)\in\left\\{0,1,-1\right\\}$, we can bound the size
$|\mathcal{L}_{r}(q)|$. Notice that $\mu(1)=1$ which implies that

$\displaystyle|\mathcal{L}_{r}(q)|$
$\displaystyle=\frac{1}{r}q^{r}+\frac{1}{r}\sum_{\begin{subarray}{c}d|r\\\
d>1\end{subarray}}\mu(d)q^{r/d}$
$\displaystyle\leqslant\frac{1}{r}q^{r}+q^{r/2}$

and similarly,

$|\mathcal{L}_{r}(q)|\geqslant\frac{1}{r}q^{r}-q^{r/2}.$

Thus, the number of Lyndon words over an alphabet of size $q$ is
$|\mathcal{L}_{r}(q)|=\frac{q^{r}}{r}\left(1+o(1)\right)$.

The length of a codeword $\mathbf{s}\in\mathcal{C}_{r}$ is bounded above by
$2r$. Thus, we obtain that

$\displaystyle R$
$\displaystyle\geqslant\frac{\log_{q}|\mathcal{L}_{r}(q)|}{2r}$
$\displaystyle=\frac{r-\log_{q}(r)+\log_{q}(1+o(1)}{2r}$
$\displaystyle=\frac{1}{2}-\frac{\log_{q}(r)}{r}+o(1)$
$\displaystyle=\frac{1}{2}(1+o(1)).$

###### Remark VIII.5

A similar encoding process can be used to reconstruct a string
$\mathbf{s}\in\mathcal{C}_{r}(n)$ when $n\geqslant 2r$. Thus, it is possible
to use $\mathcal{C}_{r}(n)$ as a code of length $n$. Applying similar
calculations with $n$ instead of $2r$, we obtain code rate $R=r/n$. Thus, when
$r=r(n)$ is a linear function of $n$, such as $r(n)=n/\alpha$ for some
$\alpha\in{\mathbb{N}}$, we obtain a rate of $1/\alpha$. If $r(n)=o(n)$ the
code rate is $0$.

##  IX Conclusion

In this paper, we firstly solved the problem on whether a string can be
uniquely reconstructed up to reversal or not, when only given its prefix-
suffix composition multiset:

  * •

we completely characterized their structures;

  * •

we give an explicit formula of their numbers;

  * •

for any given string $\mathbf{s}$, we gave a method to find all the strings
that share a common prefix-suffix composition multiset with $\mathbf{s}$, and
we gave a formula of the number of such strings.

As applications of these results, we gave a construction of composition codes
of maximum size. But we do not know whether or not there is an efficient
reconstruction algorithm to reconstruct an arbitrary string in this kind of
code. This will be an interesting problem for the future research. As a
compromise, we constructed a subcode $\mathcal{E}_{1}(n)$ of some composition
code of maximum size. For this subcode, there does exist a reconstruction
algorithm. It is shown that the redundancy of this subcode is less that
$\frac{1}{2}\log_{2}(n)+3+\frac{1}{2}\log_{2}(\pi)$.

In addition, we studied two error models of composition errors. For each error
model, we modified $\mathcal{E}_{1}(n)$ to get a composition code that can
correct the studied type of error; each code has asymptotic rate $1$.

The authors of [21] focused on the problem of uniquely reconstructing a set of
strings from the union of their prefix-suffix composition multisets. We
believe that our results in this paper might be a helpful step towards fully
understanding this problem. It is also interesting to extend our results to
this situation. Moreover, in either this paper or [21], the constructed codes
uses the idea that we can distinguish the prefix composition multiset from the
suffix composition multiset. An interesting question is whether it is possible
to construct codes without this property, such that a set of strings can be
uniquely reconstructed from the union of their prefix-suffix composition
multiset. We leave this problem for a future endeavour.

Secondly, we initiated the problem of reconstructing a string from its
composition multiset under the condition that at most a constant number of its
compositions are lost. We solved this problem for a special case when the
error is asymmetric. It is interesting to introduce new ideas to solve this
problem for more parameters and even without the ”asymmetric” assumption.

Lastly, we presented the problem of $r$-length limited composition multiset
reconstruction, and provided a simple coding scheme that obtains a rate of
$1/2$. This problem gives rise to many interesting problems. For example, is
it possible to improve the code presented in this problem for the case
$r=r(n)$ is a linear function of $n$? What about codes for a constant $r$ or
for a different functions $r(n)$? Is it possible to find bounds on the
capacity of such codes? Also, some generalizations of the model itself are of
interest. For example, consider the case in which compositions of substrings
of lengths between $r_{1}$ and $r_{2}$ are obtained, Consider the appearances
of errors, or even considering a scattered noise model in which the
compositions are obtained according to a probability which is a function of
their length. As an example, consider the case that all the compositions up to
length $r_{1}$ are obtained, and the compositions of strings of length
$r_{1}+j$ are obtained with a probability of $1/2^{j-1}$.

## References

  * [1] J. G. David Reinsel and J. Rydning, “The Digitization of the World from Edge to Core,” in _IDC Report_ , 2018. [Online]. Available: https://www.seagate.com/files/www-content/our-story/trends/files/idc-seagate-dataage-whitepaper.pdf
  * [2] G. M. Church, Y. Gao, and S. Kosuri, “Next-Generation Digital Information Storage in DNA,” _Science_ , vol. 337, no. 6102, pp. 1628–1628, Sep. 2012.
  * [3] N. Goldman, P. Bertone, S. Chen, C. Dessimoz, E. M. LeProust, B. Sipos, and E. Birney, “Towards Practical, High-capacity, Low-Maintenance Information Storage in Synthesized DNA,” _Nature_ , vol. 494, no. 7435, pp. 77–80, Feb. 2013.
  * [4] R. N. Grass, R. Heckel, M. Puddu, D. Paunescu, and W. J. Stark, “Robust Chemical Preservation of Digital Information on DNA in Silica with Error-Correcting Codes,” _Angewandte Chemie International Edition_ , vol. 54, no. 8, pp. 2552–2555, Feb. 2015.
  * [5] S. M. H. T. Yazdi, Y. Yuan, J. Ma, H. Zhao, and O. Milenkovic, “A Rewritable, Random-Access DNA-Based Storage System,” _Scientific Reports_ , vol. 5, p. 14318, Sep. 2015.
  * [6] V. Zhirnov, R. M. Zadegan, G. S. Sandhu, G. M. Church, and W. L. Hughes, “Nucleic acid memory,” _Nature Materials_ , vol. 15, no. 4, pp. 366–370, Apr. 2016.
  * [7] A. A. Ouahabi, J.-A. Amalian, L. Charles, and J.-F. Lutz, “Mass spectrometry sequencing of long digital polymers facilitated by programmed inter-byte fragmentation,” _Nature Communications_ , vol. 8, p. 967, Oct. 2017.
  * [8] S. M. H. T. Yazdi, R. Gabrys, and O. Milenkovic, “Portable and Error-Free Dna-Based Data Storage,” _Scientific Reports_ , vol. 7, p. 5011, Jul. 2017.
  * [9] M. G. T. A. Rutten, F. W. Vaandrager, J. A. A. W. Elemans, and R. J. M. Nolte, “Encoding information into polymers,” _Nature Reviews Chemistry_ , vol. 2, no. 11, pp. 365–381, Nov. 2018.
  * [10] R. Heckel, G. Mikutis, and R. N. Grass, “A Characterization of the DNA Data Storage Channel,” _Scientific Reports_ , vol. 9, p. 9663, Jul. 2019.
  * [11] C. N. Takahashi, B. H. Nguyen, K. Strauss, and L. Ceze, “Demonstration of End-to-End Automation of DNA Data Storage,” _Scientific Reports_ , vol. 9, p. 4998, Mar. 2019.
  * [12] S. K. Tabatabaei, B. Wang, N. B. Murali Athreya, B. Enghiad, A. G. Hernandez, J.-P. Leburton, D. Soloveichik, H. Zhao, and O. Milenkovic, “DNA Punch Cards: Encoding Data on Native DNA Sequences via Topological Modifications,” _bioRxiv_ , p. 672394, 2019.
  * [13] S. K. Tabatabaei, B. Wang, N. B. M. Athreya, B. Enghiad, A. G. Hernandez, C. J. Fields, J.-P. Leburton, D. Soloveichik, H. Zhao, and O. Milenkovic, “DNA punch cards for storing data on native DNA sequences via enzymatic nicking,” _Nature Communications_ , vol. 11, p. 1742, Apr. 2020.
  * [14] K. Matange, J. M. Tuck, and A. J. Keung, “DNA stability: a central design consideration for DNA data storage systems,” _Nature Communications_ , vol. 12, p. 1358, Mar. 2021.
  * [15] K. Launay, J.-A. Amalian, E. Laurent, L. Oswald, A. A. Ouahabi, A. Burel, F. Dufour, C. Carapito, J.-L. Clement, J.-F. Lutz, L. Charles, and D. Gigmes, “Precise Alkoxyamine Design to Enable Automated Tandem Mass Spectrometry Sequencing of Digital Poly(phosphodiester)s,” _Angewandte Chemie International Edition_ , vol. 60, no. 2, pp. 917–926, Jan. 2021.
  * [16] C. Pan, S. K. Tabatabaei, S. M. H. T. Yazdi, A. G. Hernandez, C. M. Schroeder, and O. Milenkovic, “DNA stability: a central design consideration for DNA data storage systems,” _Nature Communications_ , vol. 13, p. 2984, May 2022.
  * [17] J. Acharya, H. Das, O. Milenkovic, A. Orlitsky, and S. Pan, “String Reconstruction from Substring Compositions,” _SIAM Journal on Discrete Mathematics_ , vol. 29, no. 3, pp. 1340–1371, 2015.
  * [18] S. Pattabiraman, R. Gabrys, and O. Milenkovic, “Coding for Polymer-Based Data Storage,” _arXiv: 2003.02121v2_ , 2021. [Online]. Available: http://arxiv.org/abs/2003.02121v2
  * [19] A. Banerjee, A. Wachter-Zeh, and E. Yaakobi, “Insertion and Deletion Correction in Polymer-based Data Storage,” _arXiv: 2201.08612v2_ , 2022. [Online]. Available: https://arxiv.org/abs/2201.08612v2
  * [20] U. Gupta and H. Mahdavifar, “A New Algebraic Approach for String Reconstruction from Substring Compositions,” _arXiv:2201.09955v1_ , 2022. [Online]. Available: https://arxiv.org/abs/2201.09955v1
  * [21] R. Gabrys, S. Pattabiraman, and O. Milenkovic, “Reconstruction of Sets of Strings from Prefix/Suffix Compositions,” _arXiv: 2110.02352v1_ , 2021. [Online]. Available: http://arxiv.org/abs/2110.02352v1
  * [22] Ömer Eğecioğlu and A. M. Garsia, _Lessons in Enumerative Combinatorics_ , 1st ed., ser. Graduate Texts in Mathematics. Springer Cham, 2021, vol. 290.
  * [23] W. C. Huffman and V. Pless, _Fundamentals of Error-Correcting Codes_. Cambridge University Press, 2003\.
  * [24] S. Jukna, _Extremal Combinatorics_ , 2nd ed., ser. Texts in Theoretical Computer Science. An EATCS Series. Springer Berlin, Heidelberg, 2011.
  * [25] T. Koshy, _Fibonacci and Lucas Numbers with Applications (Volume 1)_ , 2nd ed., ser. Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts. John Wiley & Sons, Ltd, 2017.
  * [26] R. C. Lyndon, “On Burnside’s Problem,” _Transactions of the American Mathematical Society_ , vol. 77, no. 2, pp. 202–215, Sep. 1954.
  * [27] ——, “On Burnside’s Problem. II,” _Transactions of the American Mathematical Society_ , vol. 78, no. 2, pp. 329–332, Mar. 1955.
  * [28] C. W. Li and W. Q. Liu, “Approximation of multiple stochastic integrals and its application to stochastic differential equations,” _Nonlinear Analysis: Theory, Methods & Applications_, vol. 30, no. 2, pp. 697–708, Dec. 1997.
  * [29] K. G. Subramanian, R. Siromoney, and L. Mathew, “Lyndon trees,” _Theoretical computer science_ , vol. 106, no. 2, pp. 373–383, Dec. 1992\.
  * [30] O. Elishco, R. Gabrys, E. Yaakobi, and M. Médard, “Repeat-Free Codes,” _IEEE Transactions on Information Theory_ , vol. 67, no. 9, pp. 5749–5764, Jun. 2021.
  * [31] J. P. Duval, “Factorizing words over an ordered alphabet,” _Journal of Algorithms_ , vol. 4, no. 4, pp. 363–381, Dec. 1983.
  * [32] ——, “Génération of a section of conjugation classes and Lyndon word tree of length bornée,” _Theoretical computer science_ , vol. 60, no. 3, pp. 255–283, Dec. 1988.
  * [33] H. Crapo and D. Senato, _Algebraic Combinatorics and Computer Science: A Tribute to Gian-Carlo Rota_. Springer Science & Business Media, 2012.


* Kupiec et al. [1995] Julian Kupiec, Jan Pedersen, and Francine Chen.  A trainable document summarizer.  In _Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval_ , SIGIR ’95, pages 68–73, New York, NY, USA, 1995. ACM.  ISBN 0-89791-714-6.  doi: 10.1145/215206.215333.  URL http://doi.acm.org/10.1145/215206.215333.
  * Radev et al. [2004] Dragomir R. Radev, Hongyan Jing, Małgorzata Styś, and Daniel Tam.  Centroid-based summarization of multiple documents.  _Information Processing & Management_, 40(6):919 – 938, 2004.  ISSN 0306-4573.  doi: http://dx.doi.org/10.1016/j.ipm.2003.10.006.  URL http://www.sciencedirect.com/science/article/pii/S0306457303000955.
  * Radev et al. [2000] Dragomir R. Radev, Hongyan Jing, and Malgorzata Budzikowska.  Centroid-based summarization of multiple documents: sentence extraction, utility-based evaluation, and user studies.  In _Proceedings of the 2000 NAACL-ANLPWorkshop on Automatic summarization - Volume 4_ , NAACL-ANLP-AutoSum ’00, pages 21–30, Stroudsburg, PA, USA, 2000. Association for Computational Linguistics.  doi: 10.3115/1117575.1117578.  URL http://dx.doi.org/10.3115/1117575.1117578.
  * Agrawal and Srikant [1994] Rakesh Agrawal and Ramakrishnan Srikant.  Fast algorithms for mining association rules in large databases.  In _Proceedings of the 20th International Conference on Very Large Data Bases_ , VLDB ’94, pages 487–499, San Francisco, CA, USA, 1994. Morgan Kaufmann Publishers Inc.  ISBN 1-55860-153-8.  URL http://dl.acm.org/citation.cfm?id=645920.672836.
  * Baralis et al. [2012] Elena Baralis, Luca Cagliero, Saima Jabeen, and Alessandro Fiori.  Multi-document summarization exploiting frequent itemsets.  In _Proceedings of the 27th Annual ACM Symposium on Applied Computing_ , SAC ’12, pages 782–786, New York, NY, USA, 2012. ACM.  ISBN 978-1-4503-0857-1.  doi: 10.1145/2245276.2245427.  URL http://doi.acm.org/10.1145/2245276.2245427.
  * Baralis et al. [2015] Elena Baralis, Luca Cagliero, Alessandro Fiori, and Paolo Garza.  Mwi-sum: A multilingual summarizer based on frequent weighted itemsets.  _ACM Trans. Inf. Syst._ , 34(1):5:1–5:35, September 2015.  ISSN 1046-8188.  doi: 10.1145/2809786.  URL http://doi.acm.org/10.1145/2809786.
  * Litvak and Vanetik [2017] Marina Litvak and Natalia Vanetik.  Query-based summarization using mdl principle.  In _Proceedings of the MultiLing 2017 Workshop on Summarization and Summary Evaluation Across Source Types and Genres_ , pages 22–31, Valencia, Spain, April 2017. Association for Computational Linguistics.  URL http://www.aclweb.org/anthology/W17-1004.
  * Vreeken et al. [2011] Jilles Vreeken, Matthijs van Leeuwen, and Arno Siebes.  Krimp: mining itemsets that compress.  _Data Mining and Knowledge Discovery_ , 23(1):169–214, Jul 2011.  ISSN 1573-756X.  doi: 10.1007/s10618-010-0202-x.  URL https://doi.org/10.1007/s10618-010-0202-x.
  * Steinberger and Jezek [2004] Josef Steinberger and Karel Jezek.  Using latent semantic analysis in text summarization and summary evaluation.  In _Proc. ISIM’04_ , pages 93–100, 2004.
  * Feigenblat et al. [2017] Guy Feigenblat, Haggai Roitman, Odellia Boni, and David Konopnicki.  Unsupervised query-focused multi-document summarization using the cross entropy method.  In _Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’17, pages 961–964, New York, NY, USA, 2017. ACM.  ISBN 978-1-4503-5022-8.  doi: 10.1145/3077136.3080690.  URL http://doi.acm.org/10.1145/3077136.3080690.
  * Rubinstein and Kroese [2004] Reuven Y. Rubinstein and Dirk P. Kroese.  _The Cross Entropy Method: A Unified Approach To Combinatorial Optimization, Monte-carlo Simulation (Information Science and Statistics)_.  Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2004.  ISBN 038721240X.
  * Salton et al. [1997] Gerard Salton, Amit Singhal, Mandar Mitra, and Chris Buckley.  Automatic text structuring and summarization.  _Inf. Process. Manage._ , 33(2):193–207, March 1997.  ISSN 0306-4573.  doi: 10.1016/S0306-4573(96)00062-3.  URL http://dx.doi.org/10.1016/S0306-4573(96)00062-3.
  * Ferreira et al. [2014] R. Ferreira, F. Freitas, L. d. S. Cabral, R. D. Lins, R. Lima, G. França, S. J. Simske, and L. Favaro.  A context based text summarization system.  In _2014 11th IAPR International Workshop on Document Analysis Systems_ , pages 66–70, April 2014.  doi: 10.1109/DAS.2014.19.
  * Erkan and Radev [2004] Günes Erkan and Dragomir R. Radev.  Lexrank: Graph-based lexical centrality as salience in text summarization.  _Journal of Artificial Intelligence Research_ , 22(1):457–479, December 2004.  ISSN 1076-9757.  URL http://dl.acm.org/citation.cfm?id=1622487.1622501.
  * Mihalcea and Tarau [2004] Rada Mihalcea and Paul Tarau.  Textrank: Bringing order into texts.  In Dekang Lin and Dekai Wu, editors, _Proceedings of EMNLP 2004_ , pages 404–411, Barcelona, Spain, July 2004. Association for Computational Linguistics.  URL http://www.aclweb.org/anthology/W04-3252.
  * Brin and Page [1998] S. Brin and L. Page.  The anatomy of a large-scale hypertextual web search engine.  In _Seventh International World-Wide Web Conference (WWW 1998)_ , 1998\.  URL http://ilpubs.stanford.edu:8090/361/.
  * Li et al. [2006] Wenjie Li, Mingli Wu, Qin Lu, Wei Xu, and Chunfa Yuan.  Extractive summarization using inter- and intra- event relevance.  In _Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics_ , ACL-44, pages 369–376, Stroudsburg, PA, USA, 2006\. Association for Computational Linguistics.  doi: 10.3115/1220175.1220222.  URL https://doi.org/10.3115/1220175.1220222.
  * Wan [2007] Xiaojun Wan.  Timedtextrank: Adding the temporal dimension to multi-document summarization.  In _Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’07, pages 867–868, New York, NY, USA, 2007. ACM.  ISBN 978-1-59593-597-7.  doi: 10.1145/1277741.1277949.  URL http://doi.acm.org/10.1145/1277741.1277949.
  * Wan [2008] Xiaojun Wan.  An exploration of document impact on graph-based multi-document summarization.  In _Proceedings of the Conference on Empirical Methods in Natural Language Processing_ , EMNLP ’08, pages 755–762, Stroudsburg, PA, USA, 2008. Association for Computational Linguistics.  URL http://dl.acm.org/citation.cfm?id=1613715.1613811.
  * Kleinberg [1999] Jon M. Kleinberg.  Authoritative sources in a hyperlinked environment.  _J. ACM_ , 46(5):604–632, September 1999.  ISSN 0004-5411.  doi: 10.1145/324133.324140.  URL http://doi.acm.org/10.1145/324133.324140.
  * Yeh et al. [2008] Jen-Yuan Yeh, Hao-Ren Ke, and Wei-Pang Yang.  ispreadrank: Ranking sentences for extraction-based summarization using feature weight propagation in the sentence similarity network.  _Expert Systems with Applications_ , 35(3):1451 – 1462, 2008.  ISSN 0957-4174.  doi: https://doi.org/10.1016/j.eswa.2007.08.037.  URL http://www.sciencedirect.com/science/article/pii/S0957417407003612.
  * Quillian [1968] M. Ross Quillian.  _Semantic Memory_ , pages 227–270.  The MIT Press, 1968.
  * Liu et al. [2008] Y. Liu, X. Wang, J. Zhang, and H. Xu.  Personalized pagerank based multi-document summarization.  In _IEEE International Workshop on Semantic Computing and Systems_ , pages 169–173, July 2008.  doi: 10.1109/WSCS.2008.32.
  * Orasan and St [2007] Constantin Orasan and Stafford St.  Pronominal anaphora resolution for text summarisation.  _of: Proceedings of the Recent Advances in Natural Language Processing_ , pages 430–436, 2007.
  * Miller [1995a] George A. Miller.  Wordnet: A lexical database for english.  _Commun. ACM_ , 38(11):39–41, November 1995a.  ISSN 0001-0782.  doi: 10.1145/219717.219748.  URL http://doi.acm.org/10.1145/219717.219748.
  * Hennig et al. [2008] Leonhard Hennig, Winfried Umbrath, and Robert Wetzker.  An ontology-based approach to text summarization.  In _Proceedings of the 2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology - Volume 03_ , WI-IAT ’08, pages 291–294, Washington, DC, USA, 2008. IEEE Computer Society.  ISBN 978-0-7695-3496-1.  doi: 10.1109/WIIAT.2008.175.  URL http://dx.doi.org/10.1109/WIIAT.2008.175.
  * Ono et al. [1994] Kenji Ono, Kazuo Sumita, and Seiji Miike.  Abstract generation based on rhetorical structure extraction.  In _Proceedings of the 15th conference on Computational linguistics - Volume 1_ , COLING ’94, pages 344–348, Stroudsburg, PA, USA, 1994\. Association for Computational Linguistics.  doi: 10.3115/991886.991946.  URL http://dx.doi.org/10.3115/991886.991946.
  * Marcu [1998] Daniel Marcu.  Improving summarization through rhetorical parsing tuning.  In _In: The Sixth Workshop on Very Large Corpora_ , pages 206–215, 1998.
  * Kikuchi et al. [2014] Yuta Kikuchi, Tsutomu Hirao, Hiroya Takamura, Manabu Okumura, and Masaaki Nagata.  Single document summarization based on nested tree structure.  In _Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 315–320, Baltimore, Maryland, June 2014. Association for Computational Linguistics.  URL http://www.aclweb.org/anthology/P14-2052.
  * Goyal and Eisenstein [2016] Naman Goyal and Jacob Eisenstein.  A joint model of rhetorical discourse structure and summarization.  In _Proceedings of the Workshop on Structured Prediction for NLP_ , pages 25–34, Austin, TX, November 2016. Association for Computational Linguistics.  URL http://aclweb.org/anthology/W16-5903.
  * Wick et al. [2011] Michael L. Wick, Khashayar Rohanimanesh, Kedar Bellare, Aron Culotta, and Andrew McCallum.  Samplerank: Training factor graphs with atomic gradients.  In _Proceedings of the 28th International Conference on Machine Learning, ICML 2011, Bellevue, Washington, USA, June 28 - July 2, 2011_ , pages 777–784, 2011.
  * Osborne [2002] Miles Osborne.  Using maximum entropy for sentence extraction.  In _Proceedings of the ACL-02 Workshop on Automatic Summarization - Volume 4_ , AS ’02, pages 1–8, Stroudsburg, PA, USA, 2002. Association for Computational Linguistics.  doi: 10.3115/1118162.1118163.  URL http://dx.doi.org/10.3115/1118162.1118163.
  * Yeh et al. [2005] Jen-Yuan Yeh, Hao-Ren Ke, Wei-Pang Yang, and I-Heng Meng.  Text summarization using a trainable summarizer and latent semantic analysis.  _Inf. Process. Manage._ , 41(1):75–95, January 2005.  ISSN 0306-4573.  doi: 10.1016/j.ipm.2004.04.003.  URL http://dx.doi.org/10.1016/j.ipm.2004.04.003.
  * Amini and Gallinari [2002] Massih-Reza Amini and Patrick Gallinari.  The use of unlabeled data to improve supervised learning for text summarization.  In _Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’02, pages 105–112, New York, NY, USA, 2002. ACM.  ISBN 1-58113-561-0.  doi: 10.1145/564376.564397.  URL http://doi.acm.org/10.1145/564376.564397.
  * Wong et al. [2008] Kam-Fai Wong, Mingli Wu, and Wenjie Li.  Extractive summarization using supervised and semi-supervised learning.  In _Proceedings of the 22nd International Conference on Computational Linguistics - Volume 1_ , COLING ’08, pages 985–992, Stroudsburg, PA, USA, 2008. Association for Computational Linguistics.  ISBN 978-1-905593-44-6.  URL http://dl.acm.org/citation.cfm?id=1599081.1599205.
  * Eisenstein and Barzilay [2008] Jacob Eisenstein and Regina Barzilay.  Bayesian unsupervised topic segmentation.  In _Proceedings of the Conference on Empirical Methods in Natural Language Processing_ , EMNLP ’08, pages 334–343, Stroudsburg, PA, USA, 2008. Association for Computational Linguistics.  URL http://dl.acm.org/citation.cfm?id=1613715.1613760.
  * Daumé III and Marcu [2006] Hal Daumé III and Daniel Marcu.  Bayesian query-focused summarization.  In _Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics_ , pages 305–312, Sydney, Australia, July 2006. Association for Computational Linguistics.  doi: 10.3115/1220175.1220214.  URL http://www.aclweb.org/anthology/P06-1039.
  * Minka [2001] Thomas Minka.  A family of algorithms for approximate bayesian inference, 2001.
  * Celikyilmaz and Hakkani-Tür [2011] Asli Celikyilmaz and Dilek Hakkani-Tür.  Discovery of topically coherent sentences for extractive summarization.  In _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 1_ , HLT ’11, pages 491–499, Stroudsburg, PA, USA, 2011. Association for Computational Linguistics.  ISBN 978-1-932432-87-9.  URL http://dl.acm.org/citation.cfm?id=2002472.2002535.
  * Yang et al. [2015] Guangbing Yang, Dunwei Wen, Kinshuk, Nian-Shing Chen, and Erkki Sutinen.  A novel contextual topic model for multi-document summarization.  _Expert Syst. Appl._ , 42(3):1340–1352, February 2015.  ISSN 0957-4174.  doi: 10.1016/j.eswa.2014.09.015.  URL http://dx.doi.org/10.1016/j.eswa.2014.09.015.
  * Blei et al. [2010] David M. Blei, Thomas L. Griffiths, and Michael I. Jordan.  The nested chinese restaurant process and bayesian nonparametric inference of topic hierarchies.  _J. ACM_ , 57(2):7:1–7:30, February 2010.  ISSN 0004-5411.  doi: 10.1145/1667053.1667056.  URL http://doi.acm.org/10.1145/1667053.1667056.
  * Wang et al. [2007] Xuerui Wang, Andrew McCallum, and Xing Wei.  Topical n-grams: Phrase and topic discovery, with an application to information retrieval.  In _Proceedings of the 2007 Seventh IEEE International Conference on Data Mining_ , ICDM ’07, pages 697–702, Washington, DC, USA, 2007\. IEEE Computer Society.  ISBN 0-7695-3018-4.  doi: 10.1109/ICDM.2007.86.  URL https://doi.org/10.1109/ICDM.2007.86.
  * Ryang and Abekawa [2012] Seonggi Ryang and Takeshi Abekawa.  Framework of automatic text summarization using reinforcement learning.  In _Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning_ , EMNLP-CoNLL ’12, pages 256–265, Stroudsburg, PA, USA, 2012. Association for Computational Linguistics.  URL http://dl.acm.org/citation.cfm?id=2390948.2390980.
  * Henß et al. [2015] Stefan Henß, Margot Mieskes, and Iryna Gurevych.  A reinforcement learning approach for adaptive single-and multi-document summarization.  In _GSCL_ , pages 3–12, 2015.
  * Rioux et al. [2014] Cody Rioux, Sadid A. Hasan, and Yllias Chali.  Fear the reaper: A system for automatic multi-document summarization with reinforcement learning.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 681–690, Doha, Qatar, October 2014\. Association for Computational Linguistics.  URL http://www.aclweb.org/anthology/D14-1075.
  * Rush et al. [2015] Alexander M. Rush, Sumit Chopra, and Jason Weston.  A neural attention model for abstractive sentence summarization.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 379–389, Lisbon, Portugal, September 2015\. Association for Computational Linguistics.  URL http://aclweb.org/anthology/D15-1044.
  * Nallapati et al. [2016] Ramesh Nallapati, Bowen Zhou, Cicero dos Santos, Caglar Gulcehre, and Bing Xiang.  Abstractive text summarization using sequence-to-sequence rnns and beyond.  In _Proceedings of The 20th SIGNLL Conference on Computational Natural Language Learning_ , pages 280–290, Berlin, Germany, August 2016. Association for Computational Linguistics.  URL http://www.aclweb.org/anthology/K16-1028.
  * Jean et al. [2015] Sébastien Jean, Kyunghyun Cho, Roland Memisevic, and Yoshua Bengio.  On using very large target vocabulary for neural machine translation.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 1–10, Beijing, China, July 2015. Association for Computational Linguistics.  URL http://www.aclweb.org/anthology/P15-1001.
  * Luong et al. [2015] Thang Luong, Ilya Sutskever, Quoc Le, Oriol Vinyals, and Wojciech Zaremba.  Addressing the rare word problem in neural machine translation.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 11–19, Beijing, China, July 2015. Association for Computational Linguistics.  URL http://www.aclweb.org/anthology/P15-1002.
  * Vinyals et al. [2015] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly.  Pointer networks.  In _Advances in Neural Information Processing Systems_ , pages 2692–2700, 2015.
  * Ling and Rush [2017] Jeffrey Ling and Alexander Rush.  Coarse-to-fine attention models for document summarization.  In _Proceedings of the Workshop on New Frontiers in Summarization_ , pages 33–42, Copenhagen, Denmark, September 2017. Association for Computational Linguistics.  URL http://www.aclweb.org/anthology/W17-4505.
  * Liu et al. [2012] Yan Liu, Sheng-hua Zhong, and Wenjie Li.  Query-oriented multi-document summarization via unsupervised deep learning.  In _Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada._ AAAI Press, 2012.  URL http://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/5058.
  * Denil et al. [2014] Misha Denil, Alban Demiraj, and Nando de Freitas.  Extraction of salient sentences from labelled documents.  _CoRR_ , abs/1412.6815, 2014.  URL http://arxiv.org/abs/1412.6815.
  * Cao et al. [2015] Ziqiang Cao, Furu Wei, Li Dong, Sujian Li, and Ming Zhou.  Ranking with recursive neural networks and its application to multi-document summarization.  In _Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence_ , AAAI’15, pages 2153–2159. AAAI Press, 2015.  ISBN 0-262-51129-0.  URL http://dl.acm.org/citation.cfm?id=2886521.2886620.
  * Yousefi-Azar and Hamey [2017] Mahmood Yousefi-Azar and Len Hamey.  Text summarization using unsupervised deep learning.  _Expert Syst. Appl._ , 68(C):93–105, February 2017.  ISSN 0957-4174.  doi: 10.1016/j.eswa.2016.10.017.  URL https://doi.org/10.1016/j.eswa.2016.10.017.
  * Ren et al. [2017] Pengjie Ren, Zhumin Chen, Zhaochun Ren, Furu Wei, Jun Ma, and Maarten de Rijke.  Leveraging contextual sentence relations for extractive summarization using a neural attention model.  In _Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’17, pages 95–104, New York, NY, USA, 2017. ACM.  ISBN 978-1-4503-5022-8.  doi: 10.1145/3077136.3080792.  URL http://doi.acm.org/10.1145/3077136.3080792.
  * Jing and McKeown [1999] Hongyan Jing and Kathleen R. McKeown.  The decomposition of human-written summary sentences.  In _Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval_ , SIGIR ’99, pages 129–136, New York, NY, USA, 1999. ACM.  ISBN 1-58113-096-1.  doi: 10.1145/312624.312666.  URL http://doi.acm.org/10.1145/312624.312666.
  * Knight and Marcu [2002] Kevin Knight and Daniel Marcu.  Summarization beyond sentence extraction: a probabilistic approach to sentence compression.  _Artif. Intell._ , 139(1):91–107, July 2002.  ISSN 0004-3702.  doi: 10.1016/S0004-3702(02)00222-9.  URL http://dx.doi.org/10.1016/S0004-3702(02)00222-9.
  * Zajic et al. [2007] David Zajic, Bonnie J. Dorr, Jimmy Lin, and Richard Schwartz.  Multi-candidate reduction: Sentence compression as a tool for document summarization tasks.  _Inf. Process. Manage._ , 43(6):1549–1570, November 2007.  ISSN 0306-4573.  doi: 10.1016/j.ipm.2007.01.016.  URL http://dx.doi.org/10.1016/j.ipm.2007.01.016.
  * Cohn and Lapata [2008] Trevor Cohn and Mirella Lapata.  Sentence compression beyond word deletion.  In _Proceedings of the 22nd International Conference on Computational Linguistics - Volume 1_ , COLING ’08, pages 137–144, Stroudsburg, PA, USA, 2008. Association for Computational Linguistics.  ISBN 978-1-905593-44-6.  URL http://dl.acm.org/citation.cfm?id=1599081.1599099.
  * Filippova [2010] Katja Filippova.  Multi-sentence compression: finding shortest paths in word graphs.  In _Proceedings of the 23rd International Conference on Computational Linguistics_ , COLING ’10, pages 322–330, Stroudsburg, PA, USA, 2010\. Association for Computational Linguistics.  URL http://dl.acm.org/citation.cfm?id=1873781.1873818.
  * Filippova et al. [2015] Katja Filippova, Enrique Alfonseca, Carlos A. Colmenares, Lukasz Kaiser, and Oriol Vinyals.  Sentence compression by deletion with lstms.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 360–368, Lisbon, Portugal, September 2015\. Association for Computational Linguistics.  URL http://aclweb.org/anthology/D15-1042.
  * Hasegawa et al. [2017] Shun Hasegawa, Yuta Kikuchi, Hiroya Takamura, and Manabu Okumura.  Japanese sentence compression with a large training dataset.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 281–286, Vancouver, Canada, July 2017. Association for Computational Linguistics.  URL http://aclweb.org/anthology/P17-2044.
  * Steinberger and Ježek [2012] Josef Steinberger and Karel Ježek.  Evaluation measures for text summarization.  _Computing and Informatics_ , 28(2):1001–1026, 2012.  URL http://www.cai.sk/ojs/index.php/cai/article/view/37/24.
  * Lin and Hovy [2003] Chin-Yew Lin and Eduard Hovy.  Automatic evaluation of summaries using n-gram co-occurrence statistics.  In _Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology - Volume 1_ , NAACL ’03, pages 71–78, Stroudsburg, PA, USA, 2003. Association for Computational Linguistics.  doi: 10.3115/1073445.1073465.  URL http://dx.doi.org/10.3115/1073445.1073465.
  * Papineni et al. [2002] Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting on Association for Computational Linguistics_ , ACL ’02, pages 311–318, Stroudsburg, PA, USA, 2002\. Association for Computational Linguistics.  doi: 10.3115/1073083.1073135.  URL http://dx.doi.org/10.3115/1073083.1073135.
  * Lin [2004] Chin-Yew Lin.  Rouge: A package for automatic evaluation of summaries.  In _Proc. ACL workshop on Text Summarization Branches Out_ , page 10, 2004.  URL http://research.microsoft.com/~cyl/download/papers/WAS2004.pdf.
  * Nenkova et al. [2007] Ani Nenkova, Rebecca Passonneau, and Kathleen McKeown.  The pyramid method: Incorporating human content selection variation in summarization evaluation.  _ACM Trans. Speech Lang. Process._ , 4(2), May 2007.  ISSN 1550-4875.  doi: 10.1145/1233912.1233913.  URL http://doi.acm.org/10.1145/1233912.1233913.
  * Hovy et al. [2006] Eduard Hovy, Chin-Yew Lin, Liang Zhou, and Junichi Fukumoto.  Automated summarization evaluation with basic elements.  In _Proceedings of the Fifth Conference on Language Resources and Evaluation (LREC)_ , pages 899–902, 2006.
  * Miller [1995b] George A. Miller.  Wordnet: A lexical database for english.  _Commun. ACM_ , 38(11):39–41, November 1995b.  ISSN 0001-0782.  doi: 10.1145/219717.219748.  URL http://doi.acm.org/10.1145/219717.219748.
  * Giannakopoulos et al. [2008] George Giannakopoulos, Vangelis Karkaletsis, George Vouros, and Panagiotis Stamatopoulos.  Summarization system evaluation revisited: N-gram graphs.  _ACM Trans. Speech Lang. Process._ , 5(3):5:1–5:39, October 2008.  ISSN 1550-4875.  doi: 10.1145/1410358.1410359.  URL http://doi.acm.org/10.1145/1410358.1410359.
  * Giannakopoulos and Karkaletsis [2010] George Giannakopoulos and Vangelis Karkaletsis.  Summarization system evaluation variations based on n-gram graphs.  In _Proceedings of the Text Analysis Conference (TAC)_ , 2010.
  * Giannakopoulos and Karkaletsis [2013] George Giannakopoulos and Vangelis Karkaletsis.  _Summary Evaluation: Together We Stand NPowER-ed_ , pages 436–450.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2013.  ISBN 978-3-642-37256-8.  doi: 10.1007/978-3-642-37256-8˙36.  URL http://dx.doi.org/10.1007/978-3-642-37256-8_36.
  * Conroy et al. [2011] John M Conroy, Judith D Schlesinger, and Dianne P O’Leary.  Nouveau-rouge: A novelty metric for update summarization.  _Computational Linguistics_ , 37(1):1–8, 2011\.
  * Aslam et al. [2013] Javed A Aslam, Matthew Ekstrand-Abueg, Virgil Pavlu, Fernando Diaz, and Tetsuya Sakai.  Trec 2013 temporal summarization.  In _TREC_ , 2013.
  * Mani et al. [1999] Inderjeet Mani, David House, Gary Klein, Lynette Hirschman, Therese Firmin, and Beth Sundheim.  The tipster summac text summarization evaluation.  In _Proceedings of the ninth conference on European chapter of the Association for Computational Linguistics_ , EACL ’99, pages 77–85, Stroudsburg, PA, USA, 1999. Association for Computational Linguistics.  doi: 10.3115/977035.977047.  URL http://dx.doi.org/10.3115/977035.977047.
  * Dorr et al. [2005] Bonnie Dorr, Christof Monz, Stacy President, Richard Schwartz, and David Zajic.  A methodology for extrinsic evaluation of text summarization: Does rouge correlate?  In _in Proceedings of the ACL 2005, Ann Arbor, 2005_ , pages 1–8, 2005.
  * Dang and Owczarzak [2008] Hoa Trang Dang and Karolina Owczarzak.  Overview of the tac 2008 update summarization task.  In _Proceedings of text analysis conference_ , TAC ’08, 2008.
  * Fukusima and Okumura [2001] Takahiro Fukusima and Manabu Okumura.  Text summarization challenge : Text summarization evaluation at ntcir workshop2.  In _Proceedings of NTCIR Workshop 2_ , pages 45–50, 2001.
  * Giannakopoulos et al. [2011] G. Giannakopoulos, M. El-Haj, B. Favre, M. Litvak, J. Steinberger, and V. Varma.  Tac 2011 multiling pilot overview.  In _Proceedings of the Fourth Text Analysis Conference (TAC 2011)–MultiLing Pilot Track._ , Gaithersburg, Maryland, USA, 2011.
  * Giannakopoulos [2013] George Giannakopoulos.  Multi-document multilingual summarization and evaluation tracks in acl 2013 multiling workshop.  In _Proceedings of the MultiLing 2013 Workshop on Multilingual Multi-document Summarization_ , pages 20–28, Sofia, Bulgaria, August 2013. Association for Computational Linguistics.  URL http://www.aclweb.org/anthology/W13-3103.
  * Kubina et al. [2013] Jeff Kubina, John Conroy, and Judith Schlesinger.  Acl 2013 multiling pilot overview.  In _Proceedings of the MultiLing 2013 Workshop on Multilingual Multi-document Summarization_ , pages 29–38, Sofia, Bulgaria, August 2013. Association for Computational Linguistics.  URL http://www.aclweb.org/anthology/W13-3104.
  * Favre et al. [2015] Benoit Favre, Evgeny Stepanov, Jérémy Trione, Frédéric Béchet, and Giuseppe Riccardi.  _Proceedings of the 16th Annual Meeting of the Special Interest Group on Discourse and Dialogue_ , chapter Call Centre Conversation Summarization: A Pilot Task at Multiling 2015, pages 232–236.  Association for Computational Linguistics, 2015.
  * Kabadjov et al. [2015] Mijail Kabadjov, Josef Steinberger, Emma Barker, Udo Kruschwitz, and Massimo Poesio.  Onforums: The shared task on online forum summarisation at multiling’15.  In _Proceedings of the 7th Forum for Information Retrieval Evaluation_ , pages 21–26. ACM, 2015.
  * Qian et al. [2016] Xin Qian, Jimmy Lin, and Adam Roegiest.  Interleaved evaluation for retrospective summarization and prospective notification on document streams.  In _Proceedings of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’16, pages 175–184, New York, NY, USA, 2016. ACM.  ISBN 978-1-4503-4069-4.  doi: 10.1145/2911451.2911494.  URL http://doi.acm.org/10.1145/2911451.2911494.
  * Song et al. [2011] Wei Song, Lim Cheon Choi, Soon Cheol Park, and Xiao Feng Ding.  Fuzzy evolutionary optimization modeling and its applications to unsupervised categorization and extractive summarization.  _Expert Syst. Appl._ , 38(8):9112–9121, August 2011.  ISSN 0957-4174.  doi: 10.1016/j.eswa.2010.12.102.  URL http://dx.doi.org/10.1016/j.eswa.2010.12.102.
  * Zhang et al. [2012] Zhengchen Zhang, Shuzhi Sam Ge, and Hongsheng He.  Mutual-reinforcement document summarization using embedded graph based sentence clustering for storytelling.  _Inf. Process. Manage._ , 48(4):767–778, July 2012.  ISSN 0306-4573.  doi: 10.1016/j.ipm.2011.12.006.  URL http://dx.doi.org/10.1016/j.ipm.2011.12.006.
  * Aries et al. [2013] Abdelkrime Aries, Houda Oufaida, and Omar Nouali.  Using clustering and a modified classification algorithm for automatic text summarization.  volume 8658 of _Proc. SPIE_ , pages 865811–865811–9, 2013.  doi: 10.1117/12.2004001.  URL http://dx.doi.org/10.1117/12.2004001.
  * Carbonell and Goldstein [1998] Jaime Carbonell and Jade Goldstein.  The use of mmr, diversity-based reranking for reordering documents and producing summaries.  In _Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval_ , pages 335–336. ACM, 1998.
  * Nishikawa et al. [2012] Hitoshi Nishikawa, Tsutomu Hirao, Toshiro Makino, and Yoshihiro Matsuo.  Text summarization model based on redundancy-constrained knapsack problem.  In _Proceedings of COLING 2012: Posters_ , pages 893–902, Mumbai, India, December 2012. The COLING 2012 Organizing Committee.  URL http://www.aclweb.org/anthology/C12-2087.
  * Bhaumik et al. [2016] Hrishikesh Bhaumik, Siddhartha Bhattacharyya, and Susanta Chakraborty.  _Redundancy Elimination in Video Summarization_ , pages 173–202.  Springer International Publishing, Cham, 2016.  ISBN 978-3-319-28854-3.  doi: 10.1007/978-3-319-28854-3˙7.  URL http://dx.doi.org/10.1007/978-3-319-28854-3_7.
  * Bayomi et al. [2016] Mostafa Bayomi, Killian Levacher, M. Rami Ghorab, Peter Lavin, Alexander O’Connor, and Séamus Lawless.  _Towards Evaluating the Impact of Anaphora Resolution on Text Summarisation from a Human Perspective_ , pages 187–199.  Springer International Publishing, Cham, 2016.  ISBN 978-3-319-41754-7.  doi: 10.1007/978-3-319-41754-7˙16.  URL http://dx.doi.org/10.1007/978-3-319-41754-7_16.
  * Steinberger et al. [2007] Josef Steinberger, Massimo Poesio, Mijail A. Kabadjov, and Karel Ježek.  Two uses of anaphora resolution in summarization.  _Information Processing & Management_, 43(6):1663 – 1680, 2007.  ISSN 0306-4573.  doi: http://dx.doi.org/10.1016/j.ipm.2007.01.010.  URL http://www.sciencedirect.com/science/article/pii/S0306457307000428.  Text Summarization.
  * Gong and Liu [2001] Yihong Gong and Xin Liu.  Generic text summarization using relevance measure and latent semantic analysis.  In _Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’01, pages 19–25, New York, NY, USA, 2001. ACM.  ISBN 1-58113-331-6.  doi: 10.1145/383952.383955.  URL http://doi.acm.org/10.1145/383952.383955.
  * McKeown et al. [1999] Kathleen R. McKeown, Judith L. Klavans, Vasileios Hatzivassiloglou, Regina Barzilay, and Eleazar Eskin.  Towards multidocument summarization by reformulation: progress and prospects.  In _Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence_ , AAAI ’99/IAAI ’99, pages 453–460, Menlo Park, CA, USA, 1999. American Association for Artificial Intelligence.  ISBN 0-262-51106-1.  URL http://dl.acm.org/citation.cfm?id=315149.315355.
  * Lin and Hovy [2002] Chin-Yew Lin and Eduard Hovy.  From single to multi-document summarization: a prototype system and its evaluation.  In _Proceedings of the 40th Annual Meeting on Association for Computational Linguistics_ , ACL ’02, pages 457–464, Stroudsburg, PA, USA, 2002\. Association for Computational Linguistics.  doi: 10.3115/1073083.1073160.  URL http://dx.doi.org/10.3115/1073083.1073160.
  * Barzilay et al. [2002] Regina Barzilay, Noemie Elhadad, and Kathleen R. McKeown.  Inferring strategies for sentence ordering in multidocument news summarization.  _J. Artif. Int. Res._ , 17(1):35–55, August 2002\.  ISSN 1076-9757.  URL http://dl.acm.org/citation.cfm?id=1622810.1622812.
  * Bollegala et al. [2005] Danushka Bollegala, Naoaki Okazaki, and Mitsuru Ishizuka.  A machine learning approach to sentence ordering for multidocument summarization and its evaluation.  In _Proceedings of the Second international joint conference on Natural Language Processing_ , IJCNLP’05, pages 624–635, Berlin, Heidelberg, 2005\. Springer-Verlag.  ISBN 3-540-29172-5, 978-3-540-29172-5.  doi: 10.1007/11562214˙55.  URL http://dx.doi.org/10.1007/11562214_55.
  * Ji and Nie [2008] Donghong Ji and Yu Nie.  Sentence ordering based on cluster adjacency in multi-document summarization.  In _Proceedings of the third International Joint Conference on Natural Language Processing_ , volume 2, 2008.
  * Liu et al. [2015] Fei Liu, Jeffrey Flanigan, Sam Thomson, Norman M. Sadeh, and Noah A. Smith.  Toward abstractive summarization using semantic representations.  In Rada Mihalcea, Joyce Yue Chai, and Anoop Sarkar, editors, _HLT-NAACL_ , pages 1077–1086. The Association for Computational Linguistics, 2015.  ISBN 978-1-941643-49-5.  URL http://dblp.uni-trier.de/db/conf/naacl/naacl2015.html#0004FTSS15.
  * Palmonari et al. [2015] Matteo Palmonari, Anisa Rula, Riccardo Porrini, Andrea Maurino, Blerina Spahiu, and Vincenzo Ferme.  _ABSTAT: Linked Data Summaries with ABstraction and STATistics_ , pages 128–132.  Springer International Publishing, Cham, 2015.  ISBN 978-3-319-25639-9.  doi: 10.1007/978-3-319-25639-9˙25.  URL http://dx.doi.org/10.1007/978-3-319-25639-9_25.
  * Durrett et al. [2016] Greg Durrett, Taylor Berg-Kirkpatrick, and Dan Klein.  Learning-based single-document summarization with compression and anaphoricity constraints.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , Berlin, Germany, August 2016. Association for Computational Linguistics.