TY - CHAP
T1 - Inferring strings from graphs and arrays
AU - Bannai, Hideo
AU - Inenaga, Shunsuke
AU - Shinohara, Ayumi
AU - Takeda, Masayuki
PY - 2003
Y1 - 2003
N2 - 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 p = p1, . . . , pn of integers 1, . . . , n. Each of our three algorithms solving the above problems runs in linear time with respect to the input size.
AB - 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 p = p1, . . . , pn of integers 1, . . . , n. Each of our three algorithms solving the above problems runs in linear time with respect to the input size.
UR - http://www.scopus.com/inward/record.url?scp=13644264108&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=13644264108&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-45138-9_15
DO - 10.1007/978-3-540-45138-9_15
M3 - Chapter
AN - SCOPUS:13644264108
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 208
EP - 217
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Rovan, Branislav
A2 - Vojtas, Peter
PB - Springer Verlag
ER -