Abstract of Paper

Inferring Strings from Graphs and Arrays
by Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda

Abstract:

This paper introduces a new problem of inferring strings from graphs,
and inferring strings from arrays. Given a graph $G$ or an array $A$,
we infer a string that suits the graph, or the array, under some condition.
Firstly, we solve the problem of finding a string $w$ such that the
directed acyclic subsequence graph (DASG) of $w$ is isomorphic to a
given graph $G$. Secondly, we consider directed acyclic word graphs
(DAWGs) in terms of string inference. Finally, we consider the problem
of finding a string $w$ of a minimal size alphabet, such that the
suffix array (SA) of $w$ is identical to a given permutation of
integers $p=p_1,...,p_n$. Each of our three algorithms solving the
above problems runs in linear time with respect to the input size.