|Abstract of Paper|
Inferring Strings from Graphs and Arrays
by Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda
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.