Inferring strings from graphs and arrays

Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

47 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 = 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.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsBranislav Rovan, Peter Vojtas
PublisherSpringer Verlag
Pages208-217
Number of pages10
ISBN (Electronic)9783540406716
DOIs
Publication statusPublished - 2003

Publication series

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

Fingerprint

Dive into the research topics of 'Inferring strings from graphs and arrays'. Together they form a unique fingerprint.

Cite this