Inferring strings from graphs and arrays

Hideo Bannai; Shunsuke Inenaga; Ayumi Shinohara; Masayuki Takeda

doi:10.1007/978-3-540-45138-9_15

Inferring strings from graphs and arrays

Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Chapter

50 Citations (Scopus)

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 p = p₁, . . . , p_n of integers 1, . . . , n. Each of our three algorithms solving the above problems runs in linear time with respect to the input size.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Branislav Rovan, Peter Vojtas
Publisher	Springer Verlag
Pages	208-217
Number of pages	10
ISBN (Electronic)	9783540406716
DOIs	https://doi.org/10.1007/978-3-540-45138-9_15
Publication status	Published - 2003

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2747
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-45138-9_15

Cite this

Bannai, H., Inenaga, S., Shinohara, A., & Takeda, M. (2003). Inferring strings from graphs and arrays. In B. Rovan, & P. Vojtas (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 208-217). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2747). Springer Verlag. https://doi.org/10.1007/978-3-540-45138-9_15

Inferring strings from graphs and arrays. / Bannai, Hideo; Inenaga, Shunsuke; Shinohara, Ayumi et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Branislav Rovan; Peter Vojtas. Springer Verlag, 2003. p. 208-217 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2747).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Bannai, H, Inenaga, S, Shinohara, A & Takeda, M 2003, Inferring strings from graphs and arrays. in B Rovan & P Vojtas (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2747, Springer Verlag, pp. 208-217. https://doi.org/10.1007/978-3-540-45138-9_15

Bannai H, Inenaga S, Shinohara A, Takeda M. Inferring strings from graphs and arrays. In Rovan B, Vojtas P, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 208-217. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-45138-9_15

Bannai, Hideo ; Inenaga, Shunsuke ; Shinohara, Ayumi et al. / Inferring strings from graphs and arrays. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Branislav Rovan ; Peter Vojtas. Springer Verlag, 2003. pp. 208-217 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{4f98be8caa5545dd8585274e741e7d34,

title = "Inferring strings from graphs and arrays",

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 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.",

author = "Hideo Bannai and Shunsuke Inenaga and Ayumi Shinohara and Masayuki Takeda",

year = "2003",

doi = "10.1007/978-3-540-45138-9_15",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "208--217",

editor = "Branislav Rovan and Peter Vojtas",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

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 -

Inferring strings from graphs and arrays

Abstract

Publication series

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this