Inferring Strings from Graphs and Arrays
Hideo Bannai1 , Shunsuke Inenaga2 ,Ayumi Shinohara2,3 , and Masayuki Takeda2,31

Human Genome Center, Institute of Medical Science, University of Tokyo,
4-6-1 Shirokanedai, Minato-ku, Tokyo 108-8639, Japanbannai@ims.u-tokyo.ac.jp
2
Department of Informatics, Kyushu University 33, Fukuoka 812-8581, Japan
3
PRESTO, Japan Science and Technology Corporation (JST){s-ine, ayumi, takeda}@i.kyushu-u.ac.jp

Abstract. This paper introduces a new problem of inferring strings
from graphs, and inferring strings from arrays. Given a graph G or anarray A, we infer a string that suits the graph, or the array, under somecondition. Firstly, we solve the problem of ﬁnding a string w such that thedirected 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 ﬁnding
a string w of a minimal size alphabet, such that the suﬃx 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.

1

Introduction

To process strings eﬃciently, several kinds of data structures are often used. A
typical form of such a structure is a graph, which is specialized for a certain
purpose such as pattern matching [1]. For instance, directed acyclic subsequencegraphs (DASGs) [2] are used for subsequence pattern matching, and directed
acyclic word graphs (DAWGs) [3] are used for substring pattern matching. It
is quite important to construct these graphs as fast as possible, processing the
input strings. In fact, for any string, its DASG and DAWG can be built in linear
time in the length of a given string. Thus, the input in this context is a string,and the output is a graph.
In this paper, we introduce a challenging problem that is a ‘reversal’ of theabove, namely, a problem of inferring strings from graphs. That is, given a directed graph G, we infer a string that suits G under some condition. Firstly, we
consider the problem of ﬁnding a string w such that the DASG of w is isomorphic to a given unlabeled graph G. We show a characterization theorem thatgives if-and-only-if conditions so that a directed acyclic graph is isomorphic to
a DASG. Our algorithm inferring a string w from G as a DASG is based on thistheorem, and it will be shown to run in linear time in the size of G. Secondly, we

d
d

c

b

c

b
0

a

1

b

2

b

3

a

a

a

(a)

4

a

b

a

d
a

a
b

b

c

c

(b)

Fig. 1. (a) DASG(w) with w = abba (b) DAWG(w) with w = ababcabcd

consider DAWGs in terms of the string inference problem. We also give a lineartime algorithm that ﬁnds a string w such that the DAWG of w is isomorphic toa given unlabeled graph G.
Another form of a data structure for string processing is an array of integers.
A problem of inferring strings from arrays was ﬁrst considered by Franěk et
al. [4]. They proposed a method to check if an integer array is a border arrayfor some string w. Border arrays are better known as failure functions [5]. They
showed an on-line linear-time algorithm to verify if a given integer array is aborder array for some string w on an unbounded size alphabet. Duval et al. [6]gave an on-line linear-time algorithm for a bounded size alphabet, to solve thisproblem.
On the other hand, in this paper we consider suﬃx arrays (SAs) [7] in thecontext of string inference. Namely, given a permutation p = p1 , . . . , pn of integers 1, . . . , n, we infer a string w of a minimal size alphabet, such that the SA
of w is identical to p. We present a linear time algorithm to infer string w froma given p.

1.1

Notations on Strings

Let Σ be a ﬁnite alphabet. An element of Σ ∗ is called a string. Strings x, y, andz are said to be a preﬁx, substring, and suﬃx of string w = xyz, respectively. The
sets of preﬁxes, substrings, and suﬃxes of a string w are denoted by Preﬁx (w),Substr (w), and Suﬃx (w), respectively. String u is said to be a subsequence ofstring w if u can be obtained by removing zero or more characters from w. The
set of subsequences of a string w is denoted by Subseq(w).
The length of a string w is denoted by |w|. The empty string is denoted by ε,that is, |ε| = 0. Let Σ + = Σ ∗ − {ε}. The i-th character of a string w is denotedby w[i] for 1 ≤ i ≤ |w|, and the substring of a string w that begins at position iand ends at position j is denoted by w[i : j] for 1 ≤ i ≤ j ≤ |w|. For convenience,
let w[i : j] = ε for j < i.
For strings w, u ∈ Σ ∗ , we denote w ≡ u if w is obtained from u by one-to-one
character replacements. For a string w let Σw denote the set of the characters
appearing in w.

1.2

GraphsLet V be a ﬁnite set of nodes. An edge is deﬁned to be an ordered pair of nodes.
Let E be a ﬁnite set of edges. A directed graph G is deﬁned to be a pair (V, E).
For an edge (u, v) of a directed graph G, u is called a parent of v, and v iscalled a child of u. Let Children(u) = {v ∈ V | (u, v) ∈ E}, and Parents(v) ={u ∈ V | (u, v) ∈ E}. Node u (v, respectively) is called the head (tail, respectively) of edge (u, v). An edge (u, v) is said to be an out-going edge of node u
and an in-coming edge of node v. A node without any in-coming edges is said tobe a source node of G. A node without any out-going edges is said to be a sinknode of G.
In a directed graph G, the sequence of edges (v0 , v1 ), (v1 , v2 ), . . . , (vn−1 , vn )is called a path, and denoted by path(v0 , vn ). The length of the path is deﬁned
to be the number of edges in the path, namely, n. If v0 = vn , the path is calleda cycle. If G has no cycles, it is called a directed acyclic graph (DAG).
An edge of a labeled graph G is an ordered triple (u, a, v), where u, v ∈ V anda ∈ Σ. A path (v0 , a1 , v1 ), (v1 , a2 , v2 ), . . . (vn−1 , an , vn ) is said to spell out string
a1 a2 · · · an . For a labeled graph G, let s(G) be the graph obtained by removing
all edge-labels from G. For two labeled graphs G and H, we write as G ∼= H ifs(G) is isomorphic to s(H).
Recall the following basic facts on Graph Theory, which will be used in thesequel.
Lemma 1 (e.g. [8] pp.6-10). Checking if a given directed graph is acyclic canbe done in linear time.
Lemma 2 (e.g. [8] pp.6-8). Connected components of a given undirected graphcan be computed in linear time.
Without loss of generality, we consider in this paper, DAGs G = (V, E) withexactly one source node and sink node, denoted source and sink , respectively.
We also assume that for all nodes v ∈ V (excluding source and sink ), there
exists both path(source, v) and path(v, sink ). For nodes u, v ∈ V , let us deﬁne
pathLengths(u, v) as the multi-set of lengths of all paths from u to v, and let
depths(v) = pathLengths(source, v).

2

Inferring String from Graph as DASGThis section considers the problem of inferring a string from a given graph as anunlabeled DASG.
For a subsequence x of string w ∈ Σ ∗ , we consider the end-position of theleftmost occurrence of x in w and denote it by LM w (x), where 0 ≤ |x| ≤∗LM w (x) ≤ |w|. We deﬁne an equivalence relation ∼seq
w on Σ byx ∼seqw y ⇔ LM w (x) = LM w (y).
denote the equivalence class of a string x ∈ Σ ∗ under ∼seq
Let [x]seq
w . The directedw
acyclic subsequence graph (DASG) of string w ∈ Σ ∗ , denoted by DASG(w), isdeﬁned as follows:Deﬁnition 1. DASG(w) is the DAG (V, E) such thatV = {[x]seq| x ∈ Subseq(w)},w
seq
E = {([x]seq
w , a, [xa]w ) | x, xa ∈ Subseq(w) and a ∈ Σ}.

According to the above deﬁnition, each node of DASG(w) can be associatedwith a position of w uniquely. When we indicate the position i of a node v of
DASG(w), we write as vi .
Theorem 1 (Baeza-Yates [2]). For any string w ∈ Σ ∗ , DASG(w) is thesmallest (partial) DFA that recognizes all subsequences of w.
DASG(w) with w = abba is shown in Fig. 1 (a). Using DASG(w), we can
examine whether or not a given pattern p ∈ Σ ∗ is a subsequence of w in O(|p|)
time [2]. Details of construction and applications of DASGs can be found in theliterature [2].
Theorem 2. A labeled DAG G = (V, E) is DASG(w) for some string w oflength n, if and only if the following properties hold.
1. Path property There is a unique path of length n from source to sink .
2. Node number property |V | = n + 1.
3. Out-going edge labels property The labels of the out-going edges of eachnode v are mutually distinct.
4. In-coming edge labels property The labels of all in-coming edges of eachnode v are equal. Moreover, the integers assigned to the tails of these edges
are consecutive.
5. Character positions property For any node vk ∈ V , assume Parents(vk )= ∅. Assume vi ∈ Parents(vk ) and vi−1 ∈/ Parents(vk ) for some 1 ≤ i < k. If
the in-coming edges of vk are labeled by some character a, then edge (vi−1 , vi )is also labeled by a.
The path of Property 1 is the unique longest path of G, which spells out w.
We call this path the backbone of G. The backbone of DASG(w) can be expressedby sequence (v0 , w[1], v1 ), . . . , (vn−1 , w[n], vn ).
Lemma 3. For any two strings u, w ∈ Σ ∗ , u ≡ w if and only if DASG(u) ∼=DASG(w).
The above lemma means that, if an unlabeled DAG is isomorphic to the
DASG of some string, the string is uniquely determined except for apparent
one-to-one character replacements.
Theorem 3. Given an unlabeled graph G = (V, E), the string inference problem
for DASGs can be solved in linear time.
Proof. We describe a linear time algorithm which, when given unlabeled graph
G = (V, E), infers a string w where s(DASG(w)) is isomorphic to G. First, recall
that the acyclicity test for given graph G is possible in linear time (Lemma 1). Ifit contains a cycle, we reject it and halt. While traversing G to test the acyclicityof G, we can also compute the length of the longest path from source to sinkof G, and let n be the length. We at the same time count the number of nodes
in G. If |V | = n + 1, we reject it and halt. Then, we assign an integer i to eachnode v of G such that the length of the longest path from source to v is i. This
corresponds to a topological sort of nodes in G, and it is known to be feasible inO(|V | + |E|) time (e.g. [8] pp.6-8).
After the above procedures, the algorithm starts from sink of G. Let w bea string of length n initialized with nil at each position. The variable unlabeledindicates the rightmost position of w where the character is not determined yet,and thus it is initially set to n = |w|. At step i, the node at position unlabeled isgiven a new character ci . We then determine all the positions of the character ci
in w, by backward traversal of in-coming edges from sink towards source. To doso, we preprocess G after ordering the nodes topologically. At node vi of G, foreach vj ∈ Children(vi ) we insert vi to the list maintained in vj , corresponding toa reversed edge (vj , vi ). Since there exists exactly n + 1 nodes in G, the integers
assigned to nodes in the backbone are sorted from 0 to n. Therefore, if we startfrom source, the list of reversed edges of every node is sorted in increasing order.
Thus, given a node node, we can examine if the numbers assigned to nodes in
Parents(node) are consecutive, in time linear in the number of elements in thelist of the reversed edges of node. If they are consecutive, the next position whereci appears in w corresponds to the smallest value in the set (the ﬁrst elementin the list), and the process is repeated for this node until we reach source.
If, at any point, the elements in the set are not consecutive, we reject G and
halt. This part is based on Properties 4 and 5 of Theorem 2. If, in this process,we encounter a position of w in which a character is already determined, we
reject G and halt since if G is a DASG, for any position its character has tobe uniquely determined. After we ﬁnish determining the positions of ci in w, we
decrement unlabeled until w[unlabeled] is undetermined, or if we reach source.
If unlabeled = 0 (if not source), then the process is repeated for a new characterci+1 . Otherwise, all the characters have been determined, and we output w. Since
each edge is traversed (backwards) only once, and unlabeled is decremented atmost n times, we can conclude that the whole algorithm runs in linear time withrespect to the size of G.
3Inferring String from Graph as DAWGThis section considers the problem of inferring a string from a given graph as anunlabeled DAWG.
Deﬁnition 2 (Crochemore [9]). The directed acyclic word graph (DAWG)
of w ∈ Σ ∗ is the smallest (partial) DFA that recognizes all suﬃxes of w.
The DAWG of w ∈ Σ ∗ is denoted by DAWG(w). DAWG(w) with w =ababcabcd is shown in Fig. 1 (b). Using DAWG(w), we can examine whether
or not a given pattern p ∈ Σ ∗ is a substring of w in O(|p|) time. Details of
construction and applications of DAWGs can be found in the literature [3].

Lemma 4. For any two strings u, w ∈ Σ ∗ , u ≡ w if and only if DAWG(u) ∼=DAWG(w).
The above lemma means that, if an unlabeled DAG is isomorphic to the
DAWG of some string, the string is uniquely determined except for apparent
one-to-one character replacements.
We assume that any string w terminates with a special delimiter symbol $which does not appear in preﬁxes. Then the suﬃxes of w are all recognized atsink of DAWG(w), spelled out from source. Note that, on such an assumption,
DAWG(w) is the smallest DFA recognizing all substrings of w. It is not diﬃcult
to see that a DAWG will have the following properties.
Theorem 4. If a labeled DAG G is DAWG(w) for some string w of length n,then the following properties hold.
1. Length property For each length i = 1, . . . , n, there is a unique path fromsource to sink of length i, where n is the length of the longest path.
2. In-coming edge labels property The labels of all in-coming edges of eachnode v are equal.
3. Suﬃx property Let ui = ui [1]ui [2] . . . ui [i] be the labels of a path of lengthi from source to sink . Then ui [i − j] = w[n − j] for each j = 0, . . . , i − 1.
The above theorem gives necessary properties for a DAG to be a DAWG.
Therefore, if a DAG G does not satisfy a property of the above theorem, thenwe can immediately decide that G is not isomorphic to any DAWG.
A naïve way to check the length property would take O(n2 ) time since theni, but we here introduce how to conﬁrm thetotal lengths of all the paths is Σi=1
length property in linear time. The length property claims that depths(sink ) ={1, 2, . . . , n} holds, where n is the length of the longest path in G from source tosink . The next lemma is a stronger version of the length property, which holds
for any node.
Lemma 5. Let w be an arbitrary string of length n. For any node v in DAWG(w),the multi-set depths(v) consists of distinct consecutive integers, that is, depths(v)= {i, i + 1, . . . , j} for some 1 ≤ i ≤ j ≤ n.
Lemma 6. Length property can be veriﬁed in linear time with respect to thetotal number of edges in the graph.
Proof. If a given G forms DAWG(w) for some string w, by Lemma 5, at eachnode v, the multi-set depths(v) consists of distinct consecutive integers. Thus
depths(v) = {i, i + 1, . . . , j} can be represented by the pair i, j of the minimum
i and the maximum j. Starting from source, we traverse all nodes in a depthﬁrst manner, where all in-coming edges of a node must have been traversed to
go deeper. If a node v has only one parent node u, then depths(v) is simply
i + 1, j + 1 where depths(u) = i, j . If a node v has k > 1 parent nodes u1 ,. . . , uk , we do as follows. Let i1 , j1 = depths(u1 ), . . . , ik , jk = depths(uk ).
By Lemma 5, depths(v) = i1 + 1, j1 + 1 ∪ · · · ∪ ik + 1, jk + 1 must be equal toimin + 1, jmax + 1 , where imin = min{i1 , . . . , ik } and jmax = max{j1 , . . . , jk }.
(Remark that the union operation is taken over multi-sets.) This can be veriﬁed
by sorting the pairs i1 , j1 , . . . , ik , jk with respect to the ﬁrst component inincreasing order into i1 , j1 , . . . , ik , jk , (i1 < · · · < ik ) and checking thatj1 + 1 = i2 , . . . , jk−1
+ 1 = ik . The sorting and veriﬁcation can be done inO(k) time at each node with a radix sort and skip count trick, provided that we
prepare an array of size n before the traversal, and reuse it.
If depths(sink ) = 1, n ﬁnally, the length property holds. The running time
is linear with respect to the number of edges, since each edge is only processed
once as out-going, and once as in-coming.

Theorem 5. Given an unlabeled graph G = (V, E), the string inference problem
for DAWGs can be solved in linear time.
Proof (sketch). We describe a linear time algorithm which, when given unlabeledgraph G = (V, E), infers a string w where s(DAWG(w)) is isomorphic to G. The
algorithm is correct, provided that there exists such a string for G. Invalid inputs
can be rejected with linear time sanity checks, after the inference.
Initially, we check the acyclicity of the graph in linear time (Lemma 1), andﬁnd source and sink . Using the algorithm of Lemma 6, we verify the length
property in linear time. At the same time, we can mark at each node, its deepest
parent, that is, the parent on the longest path from source. Notice that Property 2 of Theorem 4 allows us to label the nodes instead of the edges. From
Deﬁnition 2, it is easy to see that the labels of out-going edges from source are
distinct and should comprise the alphabet Σw , and therefore we assign distinct
labels to nodes in Children(source) (the label for sink can be set to ‘$’).
The algorithm then resembles a simple breadth-ﬁrst traversal
 from sink , going up to source. For any set N of nodes, let Parents(N ) = u∈N Parents(u).
Starting with N0 = {sink}, at step i, we will consider labeling a set Ni+1 ⊆Parents(Ni ) of nodes whose construction is deﬁned below. Nodes may have multiple paths of diﬀerent lengths to the sink, and it is marked visited when it isﬁrst considered in the set. Ni+1 is constructed by including all unvisited nodes,
as well as a single deepest visited node (if any), in Parents(Ni ) (sink is also
disregarded since it cannot have a label). With this construction, we will latersee that at least one node in Ni+1 will have already been labeled, and therefore
from Property 3 of Theorem 4, all other nodes in Ni+1 can be given the samelabel. When there are no more unvisited nodes, we infer the resulting string w,
which is spelled out by longest path from source to sink . The linear run timeof the algorithm is straightforward, since it is essentially a linear time breadthﬁrst traversal of the DAG with one extra width at most (notice that redundant
traversals from visited nodes can be avoided by using only the deepest parent
node marked at each node), and the depth of the traversal is at most the lengthof the longest path from source to sink .
The claim that Ni+1 will contain at least one labeled node for all i is justiﬁed
as follows. If Ni+1 contains a node marked visited, we can use this node since
the label of nodes are always inferred when they are marked visited. If Ni+1

does not contain a visited node, it is not diﬃcult to see from its constructionthat this implies that Ni+1 represents the set of all nodes which have a path oflength i + 1 to the sink . Then, from the length property, we can see that at least
one of these nodes is labeled in the initial distinct labeling of Children(source).
If G was not a valid structure for a DAWG, s(DAWG(w)) may not be isomorphic to G. However, G is labeled at the end of the inference algorithm, andwe can check if the labeled G and DAWG(w) are congruent or not in linear time.
This is done by ﬁrst creating DAWG(w) from w in linear time [3], checking thenumber of nodes and edges, and then doing a simultaneous linear-time traversal
on DAWG(w) and labeled G. For each pair of nodes which have the same pathfrom source in both graphs, the labels of the out-going edges are compared. 
The inclusion of a single deepest visited node (if any) when constructing Ni+1
from P arents(Ni ) is the key to the linear time algorithm, because including all
visited nodes in Parents(Ni ) would result in quadratic running time, while notincluding any visited nodes would result in failure of inferring the string for some
inputs.

4

Inferring String from Suﬃx Array

A suﬃx array SA of a string w of length n is a permutation p = p1 , . . . , pn of
the integers 1, . . . , n, which represents the lexicographic ordering of the suﬃxes
w[pi : n]. Details of construction and applications of suﬃx arrays can be foundin the literature [7].
Opposed to the string inference problem for DASGs and DAWGs, the inferredstring cannot be determined uniquely (with respect to ≡). For example, for agiven suﬃx array p = p1 , . . . , pn , we can easily create a string w = w[1] . . . w[n]with an alphabet of size n, where w[i] is set to the character with the pi th lexicographic order in the alphabet. Therefore, we deﬁne the string inference problem
for suﬃx arrays as: given a permutation p = p1 . . . pn of integers 1, . . . , n, construct a string w with a minimal alphabet size, whose suﬃx array SA(w) = p.
The only condition that a permutation p = p1 . . . pn must satisfy for it to represent a suﬃx array of string w is, for all i ∈ 1, . . . n − 1, w[pi : n] ≤lex w[pi+1 : n],where ≤lex represents the lexicographic relation over strings. From the suﬃx
array, we are provided with the lexicographic ordering of each of the charactersin the string, that is, w[p1 ] ≤lex · · · ≤lex w[pn ]. Let I denote the set of integers
where i ∈ I indicates w[pi ] <lex w[pi+1 ], that is, w[pi ] is lexicographically strictly
less than w[pi+1 ]. A strict inequality w[pi ] <lex w[pi+1 ] implies that the characters of w[pi ] and w[pi+1 ] are diﬀerent, and therefore increases the alphabet size.
If w[p1 ] <lex · · · <lex w[pn ], that is, if I = {1, . . . , n − 1}, then this is the sameas in the previous example where we obtain the trivial string of alphabet size n.
If I = φ, this indicates a single character alphabet where the only possible suﬃx
array p = p1 , . . . , pn = n, . . . , 1. Our problem is to ﬁnd the smallest I where p
still holds as a suﬃx array for some string w with alphabet size |I| + 1.

Theorem 6. Given a permutation p = p1 , . . . , pn of integers 1, . . . , n, the string
inference problem for SAs can be solved in linear time.
Proof. We give a linear time algorithm to ﬁnd the smallest I deﬁned as above.
The algorithm itself is very simple: for all i = 1, . . . , n − 1, if w[pi + 1] ≤lex
w[pi+1 + 1] then i ∈ I (w[n + 1] is deﬁned to be ﬁrst in the lexicographic orderingof the alphabet). The validity of the algorithm is shown below.
Deﬁne a mapping from a position j in the string, to its lexicographic orderk, that is r1 , . . . , rn so that rj = k such that pk = j. For i ∈ 1, . . . n − 1, consider
the two suﬃxes w[pi : n] ≤lex w[pi+1 : n]. Notice that, if there exists j s.t.
w[pi + j] ≤lex w[pi+1 + j], then there must ∃k < j s.t. w[pi + k] <lex w[pi+1 + k].
Suppose for some i, w[pi + j] ≤lex w[pi+1 + j] with some j ≥ 1, and w[pi +k] ≤lex w[pi+1 + k] with all 0 ≤ k < j. If j = 1, this indicates that w[pi ] <lexw[pi+1 ] must hold in order for the lexicographic order of the suﬃxes w[pi : n] ≤lex
w[pi+1 : n] to hold, and i must be included in I. If j ≥ 2, we show that suchconditions are covered by the conditions satisﬁed with j = 1 for a diﬀerent i.
Suppose for some i, w[pi + j] ≤lex w[pi+1 + j] with some j ≥ 2, and w[pi +k] ≤lex w[pi+1 + k] with all 0 ≤ k < j. Since w[pi + j − 1] ≤lex w[pi+1 + j − 1],
we have their lexicographic order rpi +j−1 < rpi+1 +j−1 . For convenience, denotethese as r and r respectively, that is, r < r . Since we have w[pi + j] ≤lex
w[pi+1 +j], it follows that w[pr +1] ≤lex w[pr +1]. Therefore, there must exist i(r ≤ i < r ) such that w[pi +1] ≤lex w[pi +1 +1] (and thus w[pi ] <lex w[pi +1 ]),and it should belong to I. However, this condition will be found by the algorithm
which only considers the case for j = 1.

For a given permutation p = p1 , . . . , pn , let k(p) represent the size of the minimalalphabet that w can consist of, for which SA(w) = p. Interestingly, the numberofnpermutations p of length n where k(p) = k, is given by the Eulerian number
k [10]. This is because Eulerian numbers can be interpreted as the number of
permutations of length n which have k ascents (descents), in the permutation.
This is exactly the condition we check for in Theorem 6.

5Conclusions and Open Problems

In this paper we introduced a new challenging problem named string inference,
where we infer strings from given graphs or arrays. We gave linear-time algorithms to solve the problem for DASGs and DAWGs. We also extended thisscheme to arrays, and gave an algorithm that infers a string from a given suﬃx
array in linear time.
One interesting open problem is whether inferring a string from a given factor
oracle [11] can be done in linear time. The factor oracle of a string w is a DFA
that ‘at least’ accepts Substr (w), but possibly accepts some subsequences of w as
well. Factor oracles therefore can be regarded as an ‘intermediate’ data structure
between DAWGs and DASGs. To infer a string from a given unlabeled DAG asa factor oracle, we shall need to know what the language accepted by the factor

oracle of w is, but it is still unknown. Therefore, the formal deﬁnition of factor
oracles is awaited, and it would be a part of our future work as well.
We are also interested in string inference from suﬃx trees [12]. The suﬃx treeof string w is a tree structure that represents Substr(w). The point is that its edge
labels are strings (multiple characters). Also, the compact DAWG (CDAWG) [13]of w is a DAG recognizing Substr (w) with string edge labels. Therefore, to infera string from a suﬃx tree or CDAWG, we need to infer edge labels as strings
but their lengths are not given beforehand. We expect that some kinds of word
equations will be involved in this problem, and thus this class of the string
inference problem should be far more complex than those we have solved in thispaper.

References
1. Crochemore, M., Rytter, W.: Jewels of Stringology. World Scientiﬁc (2002)
2. Baeza-Yates, R.A.: Searching subsequences (note). Theoretical Computer Science78 (1991) 363–376
3. Blumer, A., Blumer, J., Haussler, D., Ehrenfeucht, A., Chen, M.T., Seiferas, J.:
The smallest automaton recognizing the subwords of a text. Theoretical Computer
Science 40 (1985) 31–55
4. Franěk, F., Gao, S., Lu, W., Ryan, P.J., Smyth, W.F., Sun, Y., Yang, L.: Verifying
a border array in linear time. J. Comb. Math. Comb. Comput. (2002) 223–236
5. Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The design and analysis of computer
algorithms. Addison-Wesley (1974)
6. Duval, J.P., Lecroq, T., Lefevre, A.: Border array on bounded alphabet. In:
Proc. The Prague Stringology Conference ’02 (PSC’02), Czech Technical University(2002) 28–35
7. Manber, U., Myers, G.: Suﬃx arrays: A new method for on-line string searches.
SIAM J. Compt. 22 (1993) 935–948
8. Atallah, M.J., ed.: Algorithms and Theory of Computation Handbook. CRC Press(1998) ISBN:0-8493-2649-4.
9. Crochemore, M.: Transducers and repetitions. Theoretical Computer Science 45(1986) 63–86
10. Graham, R., Knuth, D., Patashnik, O.: Concrete Mathematics (2nd edition). Addison Wesley (1994)
11. Allauzen, C., Crochemore, M., Raﬃnot, M.: Factor oracle: A new structure forpattern matching. In: Proc. 26th Annual Conference on Current Trends in Theory
and Practice of Informatics (SOFSEM’99). Volume 1725 of LNCS., Springer-Verlag(1999) 291–306
12. Weiner, P.: Linear pattern matching algorithms. In: Proc. 14th Annual Symposium
on Switching and Automata Theory. (1973) 1–11
13. Blumer, A., Blumer, J., Haussler, D., McConnell, R., Ehrenfeucht, A.: Complete
inverted ﬁles for eﬃcient text retrieval and analysis. Journal of the ACM 34 (1987)
578–595