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 -