Using acceptors as transducers.
We wish to use a given nondeterministic two-way multi-tape acceptor as a transducer by supplying the contents for only some of its input tapes, and asking it to generate the missing contents for the other tapes. We provide here an algorithm for assuring beforehand that this transduction always results in a finite set of answers. We also develop an algorithm for evaluating these answers whenever the previous algorithm indicated their finiteness. Furthermore, our algorithms can be used for speeding up the simulation of these acceptors even when not used as transducers. Copyright 2001 Elsevier Science B.V.
Introduction
In this paper we study the following problem: assume that we are given a
nondeterministic two-way multi-tape acceptor A and a subset X of its tapes.
We would like to use A no longer as an acceptor which receives input on all
its tapes, but instead as a kind of transducer [15, Chapter 2.7] which receives
input on tapes X only and generates as output the set of missing inputs onto
the other tapes. We then face the following two problems:
Problem 1 Can it be guaranteed that given any choice of input strings for
tapes X the set of corresponding outputs of A will always remain finite?
Problem 2 In those cases where Problem 1 can be solved positively, how can
the actual set of outputs corresponding to a given choice of input strings be
Supported by the Academy of Finland, grant number 42977.
To appear in the Theoretical Computer Science special issue on the Third International
Workshop on Implementing Automata (WIA'98).
Preprint submitted to Elsevier Preprint 18th January 2000
The motivation for studying these two problems came from string databases
[3,7,11] which manipulate strings instead of indivisible atomic entities. Such
databases are of interest for example in bioinformatics, because they allow
the direct representation and manipulation of the stored nucleotide (DNA or
sequences. While one can base a query language for these databases
on a fixed set of sequence comparison predicates, such as in for example the
PROXIMAL system [5], it would be more flexible to allow user-defined string
processing predicates as well.
If we assume an SQL-like notation [1, Chapter 7.1] for the query language,
then one possible query for such a string database might be stated as follows.
Here # rev user-defined expression which compares the strings w 1
and w 2 denoted by the variables x 1 and x 2 , say "w 2 is the reversal of w 1 ". Then
this query requests every string w 2 that is the reversal of some string w 1 currently
stored in the database table R. Note in particular that these strings w 2
need (and in general can) not be stored anywhere in the database; the query
evaluation machinery must generate them instead as needed.
We have developed elsewhere [10,11,17] a logical framework for such a query
language. This framework accommodates expressions like # rev
multidimensional extension of the modal Extended Temporal Logic suggested
by Wolper [29]. The multi-tape acceptors studied here are exactly the computational
counterparts to these logical expressions.
A given query to a database is considered to be "safe" for execution if there is a
way to evaluate its answer finitely [1, pages 75-77]. One safe plan for evaluating
the aforementioned query would be as follows, where is the string relation
accepted by A rev , a multi-tape acceptor corresponding to the expression
such acceptor is shown as Figure 1 below.)
for all strings w 1 in table R do
output every string in V
end for
Our two problems stem from these safe evaluation plans. Problem 1 is "How
could we infer from # rev that the set V is always going to be finite for
every string w 1 that could possibly appear in R?" Problem 2 is in turn "Once
the finiteness of every possible V has been ensured, how can we simulate
this A rev (e#ciently) for each w 1 to generate the V corresponding to this
We have studied elsewhere [9][17, Chapter 4.4] how solutions for Problem 1
can be used to guide the selection of appropriate safe execution plans. To this
end, Section 1.2 presents the problem in not only automata but also database
theoretic terms.
One possible solution would have been to restrict beforehand the language
for the string handling expressions such as # rev into one which ensures
this finiteness by definition, say by fixing x 1 to be the input variable, which is
mapped into the output variable x 2 as a kind of transduction [3,7]. However,
in logic-based data models [1], the use of transducers seems less natural than
acceptors, because the concept of information flow from input to output is
alien to the logical level, and of interest only in the query evaluation level.
But we must eventually also evaluate our string database queries, and then
we must infer which of our acceptors can be used as transducers, and how
to perform these inferred transductions, and thus we face the aforementioned
problems.
The rest of this paper is organized as follows. Section 1.1 presents the acceptors
we wish to use as transducers, while Section 1.2 formalizes Problem 1. Section 2
first reviews what is already known about its decidability, and then presents
our algorithms, which give su#cient conditions for answering Problem 1 in the
a#rmative. Section 3 presents then an explicit evaluation method for those
acceptors that these algorithms accept, answering Problem 2 in turn. Finally,
Section 4 concludes our presentation.
1.1 The Automaton Model
Let the alphabet # be a finite set of characters fixed in advance, let # denote
the set of all finite sequences of these characters, let # denote the empty
sequence of this kind, and let w t denote concatenating t # N copies of w # ,
as usual. We shall study relations on these sequences, or strings drawn from #
in what follows.
On the other hand, database theory often studies sequence database models
where # is taken to be conceptually infinite instead, as in for example
[7,19,22,24,25]. Then the emphasis is on data given as lists of data items provided
by the user. Conversely, our emphasis is on data given as strings in
an alphabet fixed beforehand by the database designer. In other words, our
approach fixes an appropriate alphabet # as part of the database schema,
while the list approach considers # as part of the data instead. However, our
approach has been employed even for managing list data [2].
We furthermore assume left and right tape end-markers '[' and `]' not in #.
Then we define the n th character of a given string w # with length
as
| {z }
Intuitively our automaton model is a "two-way multi-tape nondeterministic
finite state automaton with end-markers"; similar devices have been studied
by for example Harrison and Ibarra [14] and Rajlich [20]. Formally, a k-tape
Finite State Automaton (k-FSA) [11, Section 3][17, Chapter 3.1] is a tuple
(1) # is the finite alphabet as explained above;
is the number of tapes;
(3) QA is a finite set of states;
QA is a distinguished start state;
QA is the set of final states; and
is a set of transitions of the form p c1 ,. ,c k
q, where p, q # QA , each
and each d i # {-1, 0, +1}.
We moreover require that d
ensures that the heads do indeed stay within the tape area
limited by these end-markers.
A configuration of A on input #
is of the form
corresponds intuitively to the situation, where A is in state p, and each head
scanning square number n i of the tape containing string w i .
Hence we say that is a possible next configuration
of C if and only if p w1 [n1 ],. ,w k [n k ]
-# d1 ,. ,d k
Now +1 can be interpreted as
"read forward", while -1 means "rewind the tape to read the preceding square
again", and 0 "stand still". We call tape i of A unidirectional if no transition in
specifies direction -1 for it; otherwise tape i is called bidirectional instead.
A computation of A on input #
w is a sequence . of these config-
urations, which starts with the initial configuration C
each C j+1 is a possible next configuration of the preceding configuration C j .
This computation C is accepting if and only if it is finite, its last configuration
C f has no possible next configurations, and the state of this C f belongs to
FA . The language L(A) accepted by A consists of those inputs #
w, for which
there exists an accepting computation C. Note that this language is a k-fold
relation on strings in the general case.
Because A is nondeterministic, we can without loss of generality assume that
no transitions leave the final states FA . We can for example introduce a new
III
a, a

Figure

1. A 2-FSA for recognizing strings and their reversals.
state f A into QA , and set for every state p previously in
FA , and every character combination c 1 , . , c k # {[, ]}, on which there
is no transition leaving p, we add the transition p c 1 ,. ,c k
-# 0,. ,0
f A . In this way,
whenever a computation of A would halt in state p, it performs instead one
extra transition into the (now unique) new final state f A , and halts there
instead.
We often view A as a transition graph GA with nodes QA and edges In
particular, a computation of A can be considered to trace a path P within
GA starting from node s A . It is furthermore expedient to restrict attention
to non-redundant A where each state is either s A itself or on some path P
from it into some state in FA . Figure 1 presents a 2-FSA A rev in this form
b}. The language accepted by it consists of the pairs
string v is the reversal of string u: looping in state II finds the
right end of the bidirectional tape 1 without moving the unidirectional tape 2,
while looping in state III compares the contents of these two tapes in opposite
directions.
Another often useful simplification is the following way to detect mutually
incompatible transition pairs.
of k-FSA A is locally consistent if and only if every
consecutive pair
,. ,c # k
r
of transitions in satisfies the condition
This ensures that there are configurations, in which this pair can indeed be
taken; whether these configurations do ever occur in any computation is quite
another matter. For example, both tapes in Figure 1 are locally consistent. If
in particular tape i is both unidirectional and locally consistent, then given
any path
c (1,1) ,. ,c (k,1)
-# d (1,1) ,. ,d (k,1)
c (1,2) ,. ,c (k,2)
-# d (1,2) ,. ,d (k,2)
c (1,3) ,. ,c (k,3)
-# d (1,3) ,. ,d (k,3)
in GA we can construct an input string
for tape i, which allows P to be followed, if we choose
c (i,j) if (d
# otherwise.
For example in Figure 1 the w 2 from Eq. (2) spells out the sequence of transitions
taken when looping in state III. Harrison and Ibarra provide a related
construction for deleting unidirectional input tapes from multi-tape pushdown
automata [14, Theorem 2.2], while Rajlich [20, Definition 1.1] allows the reading
head to scan two adjacent squares at the same time for similar purposes.
Again the nondeterminism of A allows us to enforce Definition 1 for tape i
at the cost of expanding the size of A by a factor of (|#|
a k-FSA B with state space Q which remembers the
character under tape head i. Add for each transition p c1 ,. ,c k
-# d1 ,. ,d k
q the transitions
-# d1 ,. ,d k
to complete our construction.
1.2 The Limitation Problem
This section introduces our limitation problem [11, Definition 3.1][17, Definition
3.3] concerning the automata defined in Section 1.1.
determine if there exists a limitation
# N with the following property: if #u 1 , . ,
L(A), then
If this is the case, then we say that A satisfies the finiteness dependency [21]
These dependencies are a special case
of functional dependencies in database theory [1, Section 8.2]. Intuitively, A
is a finite representation of the conceptually infinite database table
assures that if we select rows from this table by supplying
values for the columns 1, . , k, we do always receive a finite answer. In this
way A can be used both safely and declaratively as a string processing tool
within our string database model. Thus our goal is to treat the (user-defined)
string processing operation A as just another relation as far as the database
query language is concerned; such transparency is in fact being advocated
for the forthcoming object/relational database proposal [4, pages 49-55]. We
discuss elsewhere [12] how this overall string processing mechanism of ours
relates to this proposal and how it could be incorporated into such database
management systems.
In terms of automata theory we require that for any input #u 1 , . ,
the possible outputs #v 1 , . , v l # ) l must remain a finite set. This is what
is meant by "using acceptors as transducers": we supply strings for only some
tapes (here 1, . , k) of the acceptor A, and ask it to produce us all those
contents for the missing tapes (here k would have accepted
given the known tape contents. The limitation problem is then to determine
beforehand whether this computation will always return a finite result or not.
Weber [27,28] has studied a related question whether the set of all possible
outputs on any inputs of a given transducer remains finite, and if so, what is
the maximal output length.
2 Solving the Limitation Problem
The hardness of the limitation problem has been shown to depend crucially on
the amount of bidirectional tapes in A. The problem has been shown elsewhere
to be undecidable for FSAs with two bidirectional tapes [11, Theorem 5.1][17,
Chapter 4.1]: given a Turing machine [15, Chapter 7] M one can write a corresponding
3-FSA AM with two bidirectional tapes, which accepts exactly the
tuples #u, v, w#, where v and w together encode a sequence of computation
steps taken by M on input u. Here v and w must be read twice, requiring
bidirectionality. Then asking whether AM satisfies {1} # {2, 3} amounts to
asking whether M is total. This read-twice construction is reminiscent of representing
the valid computations of a given Turing machine as an intersection
of two Context-Free Languages [15, Chapter 8.6], and shows that it is also
undecidable to determine whether a given finiteness dependency is satisfied
by the intersection of the relations denoted by two given FSAs, even when
these FSAs have no bidirectional tapes at all [17, Corollary 6.1].
On the other hand, the limitation problem becomes decidable if we restrict attention
to those FSAs with at most one bidirectional tape [11, Theorem 5.2][17,
Chapter 4.2]. Intuitively, all the unidirectional tapes are first made locally con-
sistent, after which Eq. (2) allows us to construct their contents at will, so that
we can concentrate on the sole bidirectional tape. This tape can in turn be
studied by using an extension of the well-known crossing sequence construction
[15, Chapter 2.6] for converting two-way finite automata into classical one-way
iii
iii
iii
a, a

Figure

2. A crossing behavior of the 2-FSA in Figure 1.
finite automata. This method is clearly impractical, however. Therefore this
paper presents in Section 2.1 a practical partial solution, which furthermore
applies even in some cases involving multiple bidirectional tapes. Section 2.2
then develops this solution further to yield yet more explicit limitation information

Example 3 The 2-FSA A rev in Figure 1 satisfies both {1} # {2} and {2} #
{1} with the same limitation function the reversal of a
string is no longer than the string itself. This is moreover decidable, because
only tape 1 is bidirectional in A rev . To see how limitation inference proceeds
consider Figure 2, which exhibits the crossing behavior of A rev when tape 1
contains the string ab. For example, determining {2} # {1} involves checking
that every character written onto the bidirectional output tape 1 is "paid for"
by reading something from the unidirectional input tape 2 as well, although this
payment may occur much later during the computation; here it occurs when
tape 1 is reread in reverse. This can in turn be seen from the automaton B
produced by the crossing sequence construction by noting that the loops of B
around the repeating crossing sequence indicated in Figure 2 consume tape 2
as well.
The 2-FSA A rev is also considered to satisfy the trivial finiteness dependency
by definition. On the other hand, A rev does not satisfy # {1, 2},
because
2.1 An Algorithm for Determining Limitation
Our technique for solving the limitation problem given in Definition 2 is
based on the following two observations. Let A be the
l} the finiteness dependency in question.
Observation 1 If A accepts some input #w 1 , . , w k+l # with some computation
never visits the corresponding right
end-marker ']', then A also accepts all the su#xed inputs
with the same C. Hence, A cannot satisfy # in this case.
Observation 2 If on the other hand every accepting computation of A visits
the right end-marker ']' on all output tapes, then the only way A can violate
# is by looping while generating output onto some output tape but without
"consuming" any of the inputs at the same time - that is, by returning again
and again to read the same squares of the input tapes.
However, the (un)decidability results mentioned in the beginning of this section
indicate that reasoning about actual computations is infeasible. Thus we
reason instead about the structure of the transition graph GA . Therefore, instead
of Observation 1, the algorithm in Figure 3 merely tests that there is
no path P from the start state s A into a final state, which never requires ']'
to appear on some output tape, whereas it would have su#ced to show that
no such P is ever traversed during any accepting computation. (B denotes the
Boolean type with values 0 as 'false' and 1 as `true'.)
Similarly, the algorithm in Figure 4 enforces a more stringent condition than
Observation 2: every cycle L in GA , during which some output tape is advanced
to direction +1, must also move some input tape i into direction 1
but not back into the opposite direction #1. Then this tape i acts as a clock,
which eventually terminates the potentially dangerous repetitive traversals
of L. Again, if A violates #, then some L # failing this condition must exist in
GA , but the converse need not hold, because repetitions of L # need not necessarily
occur during any accepting computation of A; Figure 6 presents a loop
which seems at first glance to generate arbitrary many copies of character 'a'
onto its output tape 2, because it seems to move back and forth on its input
tape 1. However, closer scrutiny reveals that this behavior is in fact impossible
because the same square on tape 1 must first contain character 'a' in order to
get into state q, but later character 'b' in order to get back into state p.
Making the tapes locally consistent as in Definition 1 will catch some of these
impossible transition sequences, including all cases that arise due to the demands
on the contents of the unidirectional tapes. On the other hand, Figure 6
presents a bidirectional tape 1 which is already locally consistent but still im-
possible. If there is just one bidirectional tape altogether, then the crossing
sequence construction alluded to above in Example 3 can be seen as a method
for detecting these impossibilities and eliminating them from further consid-
eration. Unfortunately, we have no method of this kind for the general case.
The more stringent condition given above is enforced by repeatedly deleting
those transitions, which can justifiably be argued not to take part in any
loops of the kind mentioned in Observation 2. This technique is related to
analyzing the input-output behavior of logic programs [16,26], which analyze
the call graph of the given program component by component. However, our
technique remains simpler, because our automata are more restricted than
general logic programs.
function halting( G :transition graph GA of a k-FSA A;
X:subset of {1, . , k}):B;
2: for all i # {1, . , k} \ X do
3: H # G without transitions that specify ']' for tape
4: b # b # (H contains no path from s A into any state in FA )
5: end for
return b

Figure

3. An algorithm for testing Observation 1.
function looping( G:subgraph of GA for a k-FSA A;
X:subset of {1, . , k}):B;
2: H 1 , . , Hm # the maximal strongly connected components of G;
3: Delete from G all transitions between di#erent components (a.);
4: for all i # 1, . , m do
5: if some tape j # X winds to direction 1 in H i but not to #1 then
Delete from H i all transitions that wind this tape j (b.);
7: d # looping(H i , X)
8: else
9: d # no tape in {1, . , k} \ X winds into direction +1 in H i
12: end for
13: return b

Figure

4. An algorithm for testing Observation 2.
function limited( A :k-FSA;
X:subset of {1, . , k}):B;
1: return halting(G A , X) # looping(G A , X)

Figure

5. An algorithm for determining limitation.
a, a
a, a
a, a
b, a

Figure

6. A loop that cannot be traversed repeatedly.
More precisely, the edge deletions made by the algorithm in Figure 4 can be
justified as follows. Consider the first call made by the main algorithm in

Figure

5. Every loop mentioned in Observation 2 must clearly be contained in
some component H i of the entire transition graph of the k-FSA A.
(a) A transition between two di#erent strongly connected components cannot
then surely belong to any loop of this kind. The deletions in step 3 are
therefore warranted.
(b) Any transition # that winds the clock tape j selected for the current
component H i cannot belong to any loop of this kind either, because #
cannot be traversed indefinitely often. These traversals will namely wind
the input tape j eventually onto either end-marker, because tape j is not
wound into the opposite direction by any other transition # in H i . The
deletions in step 6 are therefore warranted as well.
This reasoning can then be applied in the subsequent recursive calls on the
reduced components H i as well, because we can then assume inductively that
the loops broken during the earlier calls could not have been ones mentioned
in Observation 2.
Formalizing this reasoning shows that the algorithm in Figure 5 is indeed
correct as follows.
Theorem 4 Let A be a (p
and let the algorithm in Figure 5 return 1 on A and {1, . ,
satisfies {1, . , with the function
where
Y
PROOF. Let us assume that C is an arbitrary computation of A on some input
We begin by proving the following
two claims about this C which correspond to Observations 1 and 2.
If C is accepting, then for every tape p r the
computation C takes some transition which requires ']' on tape j.
Let otherwise h be a tape which violates this Claim 5. C traces a path through
GA from s A into some state in FA . Then step 4 of the algorithm in Figure 3 sets
which violates our assumption that the algorithm in

Figure

returns 1, thus proving this Claim 5.
moves to direction +1 more than
times during the computation C.
Assume to the contrary that some h violates this Claim 6. Post a fence between
two adjacent configurations C g and C g+1 in C whenever tape
to direction +1. By our contrary assumption, at least l + 1 of these fences
are posted. Consider on the other hand two configurations C x and C y of C
to have the same color if and only if they share the same state and the same
head positions for tapes 1, . , most l of these colors are available,
recalling the assumption that tapes 1, . , p are unidirectional. Therefore C
must contain two configurations C x and C y which have the same color but are
separated by an intervening fence. Consider then the sequence of transitions
which transform C x into C y , as a path L within GA . This L forms a closed
cycle, and tape heads 1, . , are on the same squares both before and
after traversing L, because C x and C y shared a common color. Let us then see
which of the steps 3 or 6 of the algorithm in Figure 4 will first delete some
transition that belongs to L. It cannot be step 3, because all of L belongs
initially to the same maximal strongly connected component. But it cannot
be step 6 either, because if L ever moves a tape j # X into some direction 1,
it must also move tape j into the opposite direction #1 as well, in order to
return its head onto the same square both before and after L. Hence L persists
untouched to the very end of the recursion on step 9, and there the presence
of the transition of L that crosses the fence between C x and C y yields
which subsequently violates our assumption that the algorithm in Figure 5
returns 1, thus proving this Claim 6.
Claims 5 and 6 are combined into a proof of the theorem as follows. Assume
that #z # L(A); that is, A has some accepting computation C on input #z. It
su#ces to show that |w h | # l - 1 for every 1 # h # r. Tape head
must cross every border between two adjacent tape squares from left to right,
because otherwise C would not meet Claim 5. Claim 6 states in turn that C
performs at most l crossings of this kind. This means that tape p
contains at most l squares, of which the first and the last are reserved for
the end-markers, leaving at most l - 1 squares for the characters of the input
string w h . #
Example 7 Consider the 2-FSA A rev in Figure 1. The algorithm in Figure 5
can detect that it satisfies {1} # {2} as follows. The algorithm in Figure 3
returns 1, because every path into the final state IV must contain III [,]
-# 0,0
IV.
Evaluating the algorithm in Figure 4 proceeds in turn as follows. First, all transitions
from one state into another are deleted in step 3, leaving only the loops
ii
iii
a, a

Figure

7. The division of the 2-FSA in Figure 1 into components.
around states II and III. This is depicted in Figure 7, where the components
themselves are dotted, and the transitions between them (and thus deleted in
step are dashed. These loops are in turn deleted in step 6 when processing
the corresponding components, and therefore this function eventually returns
1 as well. However, Theorem 4 provides a rather imprecise limitation function
compared to the one given in Example 3.
On the other hand, the algorithm in Figure 5 fails to detect {2} # {1}, which
was detected in Example 3: looping in state II advances tape 1 without moving
tape 2, and seems therefore dangerous to the algorithm in Figure 4. Intuitively,
A rev first guesses nondeterministically some string, and only later verifies its
guess against the input. In Example 3, crossing sequences were examined to
see that this later checking in state III indeed reduces the acceptable outputs
into only finitely many (here just one).
Essentially the same limitation function as in Theorem 4 su#ces whenever all
of the output tapes r to be limited are unidirectional,
even if {1, . , cannot be verified by the
algorithm in Figure 5 [9, Theorem 2.1]. This is natural, because the algorithm
in

Figure

5 ignored the e#ects of moving any output tape p+q+1, . , p+q+r
into direction -1.
Theorem 8 Let p+1, . , p+q be all the bidirectional tapes in the (p+q+r)-
FSA A, and let A satisfy
Then
is a corresponding limitation function, where g A is as in Theorem 4.
PROOF. Consider the proof of Theorem 4, and assume further in Claim 6
that all the output tapes p+q+1, . , p+q+r are made locally consistent as in
Definition new assumption introduces the factor (|#|+2) r into W # . With
this modification, the original fencing-coloring construction shows that if some
accepting computation C on input #z advances some output tape p+q+h more
than then the path of transitions
taken by this C can be partitioned into three sub-paths KLM where L begins
in C x and ends in C y which share the same color and contains a transition #
that crosses some fence between C x and C y . However, now A must also accept
all the pumped inputs
where t # N, and each w (k,J ) denotes the string of characters in those squares
of output tape which the head lands during J (']' excluded).
This is in e#ect an application of Eq. (1) to the output tapes p+q+1, . , p+
r. The presence of # within L shows that w (h,L) #, and hence # fails by
observation 2, thereby proving this modified Claim 6.
5 continues to hold, as reasoned in Observation 1, and the theorem
follows again as before. #
Turning now to assessing when the algorithm in Figure 5 does detect finiteness
dependencies we see that it is successful at least when all tapes are unidirectional

Theorem 9 Let A be a non-redundant l)-FSA with all tapes unidirectional
and locally consistent, and let the algorithm in Figure 5 return 0 on A
and {1, . , k}. Then A does not satisfy
PROOF. The non-redundancy of A and the unidirectionality and local consistency
of all its tapes imply by Eq. (2) that for every path P in GA we
can always find an accepting computation C on some input #
traversing P.
Letting P then be any subgraph of GA which caused the algorithm in Figure
5 to return 0 yields some C whose existence violates # along the lines of
Theorem 8. #
2.2 Two Variants of the Limitation Algorithm
This section explores two possible directions into which the algorithm given
in Section 2.1 could be developed further. They both alter the non-recursive
step 9 of the algorithm in Figure 4, which tests some strongly connected
component H i in the transition graph GA of A. Moreover, this H i is known
not to be shrinkable further by the algorithm.
The first direction enlarges the set of FSAs A and finiteness dependencies #
that can be verified to hold by relaxing this test as follows. Suppose H i contained
some output tape j # {1, . , k} \ X that is wound into the reverse
if some tape j # X winds to direction 1 in H i but not in direction #1
then
Delete from H i all transitions that wind this tape j (b.);
else if some tape j # {1, . , k} \ X winds to direction -1 in H i but not
in direction +1 then
Delete from H i all transitions that wind this tape j;
else
d # no tape in {1, . , k} \ X winds into direction +1 in H i

Figure

8. The enlarging additions to the algorithm in Figure 4.
direction -1 but not into the forward direction +1. Then this tape j can again
be used as a clock for shrinking H i further, similarly to steps 5-7, because the
head on tape j cannot travel backwards forever, but must stop at least once
the left end-marker '[' is reached.
Algorithmically this direction leads to replacing steps 5-10 of the algorithm
in

Figure

4 with the steps given in Figure 8.
The other direction into which the algorithm given in Section 2.1 can be developed
is to constrain further the set of FSAs A and finiteness dependencies #
that can be verified to hold by restricting the test performed on step 9 of the
algorithm in Figure 4 to require that the component H i being tested must not
have any transitions left. Call the correspondingly modified limitation algorithm
of Section 2.1 fastidious; it thus requires that all the transitions of A
are deleted in order to verify #.
Example 10 The calculations in Example 7 show that the 2-FSA A rev in

Figure

does actually satisfy the finiteness dependency {1} # {2} even fas-
tidiously.
One advantage of fastidious verification is more e#cient simulation of A, as
will be explained in Section 3.1. The rest of this section explains another ad-
vantage, namely that it enables straightforward construction of better explicit
limitation functions than the generic one provided by Theorem 4. This construction
is similar in spirit to van Gelder's analysis of logic programs with
systems of equations [26], except that recurrences are used instead.
Let therefore A be a satisfying the finiteness dependency
suitable limitation function
would evidently be
if each auxiliary function f p
limit to the character position on output tape k+j where the right end-marker
']' is encountered. Here A is assumed to be in state p # QA , each of its input
tapes of an unspecified input string
with length m i # N and its designated output tape k + j on character h of
some unspecified output string.
These auxiliary functions can in turn be obtained by labeling the transition
graph GA of A with suitable expressions as follows:
. The expression for a state p # QA is the maximum of the expressions for
those transitions # that leave from p:
leaves from p
Graphically speaking, one can consider each node p of graph GA to become
labeled with the operator 'max' applied to the arrows that exit from p.
. The expression for a transition # is the expression for the state that
# enters, adjusted with the e#ects of # on the tapes in question:
f
where
Here the "otherwise" branch of Eq. (5) denotes the case when the transition
cannot apply by virtue of some input tape head position n i violating its
corresponding restriction # i . Then the value 1 is warranted, because it is
the earliest possible position in which ']' can possibly appear.
Graphically speaking, this shows how to construct the expressions for the
arrows maximized by node p of graph GA in Eq. (4) above.
Fastidiousness guarantees that this labeling does indeed yield a function: otherwise
the expression for some f p
refers (indirectly)
back to itself with no change to its arguments n 1 , . , n k . This, however,
implies a cycle C in GA from p back to itself for which none of the input
tapes 1, . , k moves in exactly one direction. This in turn means that C
could not be deleted by the fastidious limitation algorithm after all.
Accordingly, if a fastidious version of the algorithm in Figure 8 is used instead,
the labeling must then include all of h 1 , . , h l instead of just h, because then
also the output tapes k+1, . , k+l may have been used in deleting transitions
from the (k in question, and thus these output tape head positions
might be the ones that cannot repeat as arguments for some expression.
On the other hand, dropping the fastidiousness restriction does not altogether
invalidate this approach either, it just makes it more di#cult to provide an
explicit counterpart for Eq. (4). It is namely now possible that the expression
for some f p
does indeed refer back to itself without
changing its arguments n 1 , . , the expressions f #
j of Eq. (5) for the
transitions # that still remain in the component containing state p even after
the successful execution of the algorithm in Figure 4. However, these expressions
are also guaranteed not to increase h, for otherwise the execution of
the algorithm in Figure 4 would have been unsuccessful. Thus a function for f p
does still exist, even though giving an explicit expression for it is di#cult.
A similar labeling technique su#ces even for the crossing sequence construction
mentioned in Example 3 instead of a fastidious algorithm from Section 2.1,
provided that the labeling is performed relative to the resulting crossing sequence
automaton instead of the original [17, Chapter 5.2].
Example 11 The labeling to generate Eq. (3) for Example 10 proceeds as
follows. Applying Eq. (5) to the transitions leaving state III leads to
f
III
-# 0,0
IV
f
III
a,a
III
III
b,b
III
f III
which appear in Eq. (4) for state III, namely
f III
f
III
-# 0,0
IV
III
a,a
III
f
III
b,b
III
f III
a, a
a, a
a, a

Figure

9. A bidirectional loop that eventually ends.
where the last simplification solves the recurrence found above for f III
1 . Continuing
similarly for state II leads eventually to the tight limitation function
mentioned in Example 3.
A di#erent possibility for improving on the limitation algorithm given in Section
2.1 would be to take into account not only the directions but also the
total amount of tape movement. For instance, the current algorithms will not
break a loop like in Figure 9, because the input tape 1 in question moves in
both directions, even though the overall net e#ect of these movements is +1,
or to move one square forward, and therefore the loop cannot execute indefi-
nitely. Calculating such net e#ects have been recently studied in [18], but the
resulting algorithms di#er significantly from the approach presented here.
3 Evaluation of the Limited Answers
After inferring that the given (k does indeed satisfy the given
finiteness dependency want to
generate the (finite) set of outputs
#, or to solve Problem 2. This problem is known to be di#cult in
the general case: let B be a 2-FSA with an unidirectional input tape 1 and
a bidirectional output tape 2, and ask if a given input u can produce any
output v. This problem is equivalent to whether B, considered as a checking
stack automaton, accepts u [20, Theorem 5.1] which is known to be either
PSPACE- or NP-complete, depending on whether B # is a part of the instance or
not [6, Problem AL5]. However, the additional information # provides certain
optimization possibilities.
A straightforward way to obtain an evaluation algorithm is to convert the
output tapes from read-only into write-once, and perform these writing operations
concurrently with the simulation of the nondeterministic control. Figure
shows the resulting algorithm where the simulations of all the possible
computations are performed in a depth-first order using a stack S. The algorithm
maintains for each 1 # j # l an extensible character array W j [0 . L j
which holds the contents for the tape squares the output head k + j has al-
procedure simulate( A :(k
2:
3:
4: Initialize stack S to contain #0; L 1 , . , L l #
5: while S is nonempty do
l # be top element in S, and let # t
7: if q # FA then
8: output(v 1 , . , v l ) where each
10: else if t > |T A | then
13: Pop o# the top element from
15: else if #
-# d1 ,. ,d k ,e 1 ,. ,e l
l on which
19:
21: else
23: end if
24: end while

Figure

10. An algorithm for using acceptors as transducers.
ready examined during the computation C of A currently being simulated.

Figure

11 shows the indices during one simulation of the 2-FSA A rev from

Figure

1, where the input tape 1 contains the string ab whose reversal is being
generated onto the output tape 2.
In

Figure

10, is enumerated as # 1 , . , # |T A | , and # 0 is a new starting pseudo-
transition
-# 0,. ,0
s A . We also assume as in Section 1.1 that no final state
in FA has any outgoing transitions.
Note that # alone does not guarantee that the algorithm in Figure 10 halts, it
just guarantees that only finitely many di#erent outputs are ever generated.
Consider namely the situation in Figure 12, where the 2-FSA A rev in Figure 1
output tape 2: [ b
iii
state:

Figure

11. Simulating the 2-FSA in Figure 1 as a transducer.
input tape 2: [ b a ]
output tape 1: [ a a a    a
ii
state:

Figure

12. Generating an indefinitely long output with the 2-FSA in Figure 1.
is being used as a transducer in the opposite direction to Figure 11: input is
read from tape 2 and written onto tape 1. As explained in Example 7, A rev
is now guessing nondeterministically a possible output for later verification
against the input. But how long guesses should A rev be allowed to make?
This question can be answered by adding the extra conditions
for each 1 # j # l into branch 15 of the algorithm in Figure 10 where W is
a limitation function corresponding to #. This addition is warranted, because
if during the currently simulated computation C some j violates Eq. (6) then
more than W(|u 1 | , . , |u k |) characters from # have been output onto tape k+
j. In this case C must be eventually rejecting and can hence be discarded at
once without further ado.
Now that the L j have been bounded by W the stack S will always contain only
finitely many di#erent configurations C of the transducer being simulated on
input #u. (These transducer configurations C can be defined in a straightforward
way by extending the acceptor configurations defined in Section 1.1 with
write-once output tapes.) Although stack S represents these configurations C
only implicitly, they can be reconstructed as in branch 10 of the algorithm in

Figure

10. However, some of these configurations C can still repeat, because
the transducer being simulated can also loop on the already known parts of its
tapes without generating new output. Fortunately this looping can be detected
and eliminated simply by testing in branch 15 of the algorithm in Figure 10
that the new configuration C new being pushed into stack S does not yet occur
in stack S. This is a standard way to avoid repetition during a depth-first
search [23, Chapter 3.6]. We have also experimented with comparing C new
against all the configurations C encountered so far in the entire search conducted
by the algorithm in Figure 10 on the current input #u, but this proved
to be extremely ine#cient in practice.
Now we have solved Problem 2 by developing a halting variant of the evaluation
algorithm in Figure 10. However, this solution su#ers from two drawbacks.
Drawback 1 The value of a limitation function is needed in Eq. (6) to estimate
- and hopefully tightly - the depth at which ultimately rejecting output-
generating computations can be pruned.
This could be termed the "compile-time" drawback: the limitation function
must be formed when the acceptor is proposed as a possible transducer, while
its value is required before each invocation of the simulation algorithm in

Figure

10.
Drawback 2 The whole stack S must be scanned against repeating configurations
C when pushing each new configuration C new in the algorithm in

Figure

10.
This could in turn be termed the "run-time" drawback, because it adds loop
checking overhead the execution of the simulation algorithm in Figure 10.
Fortunately both of these drawbacks can be alleviated by considering how #
was inferred to hold, as discussed in the remainder of this section.
3.1 When the Limitation Algorithm Succeeds
Consider first the case where # was inferred to hold by having the algorithm
in

Figure

return 1 on A and #. Claim 6 in the proof of Theorem 4 shows
that every computation C of A is "self-limiting" in the sense that no L j can
grow indefinitely. Thus Eq. (6) is not needed after all, thereby alleviating
Drawback 1.
alleviates also Drawback 2. Two occurrences C x and C y of the same
configuration during C have the same color by definition. The proof of the
claim shows that C x and C y can only arise by traversing a closed loop L,
which is not deleted during the algorithm in Figure 4. We therefore modify
this algorithm to mark in A the transitions it considers deleted. Then the
algorithm in Figure 10 can stop scanning its stack S as soon as the most
recent marked transition is seen. This holds even when the marking has been
performed by the enlarged algorithm in Figure 8.
This reasoning shows another benefit of the fastidious variant of the algorithm
in

Figure

4: then every transition gets marked, and therefore scanning the
stack S is no longer required at all. That is, the algorithm in Figure 10 su#ces
unmodified in this case, and all run-time loop checking overhead has been
eliminated.
Example 12 Applying this modified marking algorithm in Figure 4 into the
2-FSA A rev in Figure 1 and even fastidiously by Example
10. Then the algorithm in Figure 10 and A rev can generate the reversal
of any given string in linear time with respect to its length. In other words,
choosing this evaluation strategy leads into an optimal way to perform string
reversals.
Note finally that this marking technique can also speed up the simulation of
those m-FSAs B which are still used as acceptors and not transducers: just
compute the marking given by the modified algorithm in Figure 4 with B and
{1, . , m} (which yields 1), and use the resulting stack scanning optimization
strategy during the simulation of B on any given input #u 1 , . , um #. Again
the marks identify transitions under which it is not necessary to look when
scanning the stack for repeating configurations during the simulation.
3.2 When All the Outputs are Unidirectional
Another strategy related to the one developed in Section 3.1 works when all
the output tapes of A are unidirectional and the finiteness dependency # still
holds but this fact can no longer be inferred by the algorithm developed in
Section 2.1.
In this case the proof of Theorem 8 shows that a halting but still correct variant
of the simulation algorithm in Figure 10 can be obtained by adding into its
branch 15 the extra condition that configurations C x and C y of the same color
- in the sense of that proof - may not repeat within any computation C: if the
path L of transitions from C x into C y advances any of the unidirectional output
tapes r, then this C must be rejecting because it would
violate # via Observation 2, while otherwise taking L during C was unnecessary
because then C x and C y are the same configuration. This reasoning provides
the loop checking discipline which guarantees the halting of the simulation
algorithm in this case.
Furthermore, this simulation is also amenable to the stack scanning optimization
technique developed in Section 3.1: a variant of the algorithm in Figure 4
which merely attempts to mark every transition it possibly can - instead of
trying to test for # and fail - identifies some of those cycles L that can cause
some color to repeat. These marks can then again be used for limiting stack
scanning during simulation.
Conclusions
We studied the problem of using a given nondeterministic two-way multi-tape
acceptor as a transducer by supplying inputs onto only some of its tapes, and
asking it to generate the rest. We developed a family of algorithms for ensuring
that this transduction does always yield finite answers, and another family of
algorithms for actually computing these answers when they are guaranteed to
exist. In addition, these two families of algorithms provided a way to execute
and optimize the simulation of nondeterministic two-way multi-tape acceptors
by restricting the amount of work that must be performed during run-time
loop checking.
These algorithms have been implemented in the prototype string database
management system being developed at the Department of Computer Science
in the University of Helsinki [8,12,13].



--R

Foundations of Databases.

Datalog and transducers.
Foundation for Object/Relational Databases - The Third Manifesto
PROXIMAL: a database system for the e
Computers and Intractability: A Guide to the Theory of NP-Completeness
Regular sequence operations and their use in database queries.
AQL: An alignment based query language for querying string databases.
translation and evaluation of Alignment Calculus.
Reasoning about strings in databases.
Reasoning about strings in databases.
A declarative programming system for manipulating strings.
Implementing a declarative string query language with string restructuring.

Introduction to Automata Theory
A framework for testing safety and e

Finding paths with the right cost.

Absolutely parallel grammars and two-way finite-state transducers
Safety of recursive Horn clauses with infinite relations (extended abstract).
Supporting lists in a data model (a timely approach).
Artificial Intelligence: a Modern Approach.
SEQ: A model for sequence databases.
The AQUA approach to querying lists and trees in object-oriented databases
Deriving constraints among argument sizes in logic programs.
On the valuedness of finite transducers.
On the lengths of values in a finite transducer.
Temporal logic can be more expressive.
--TR
A database language for sets, lists and tables
Safety of recursive Horn clauses with infinite relations
On the valuedness of finite transducers
On the lengths of values in a finite transducer
Reasoning about strings in databases
Artificial intelligence
A framework for testing safety and effective computability
Foundation for object/relational databases
Regular sequence operations and their use in database queries
Sequences, datalog, transducers
Reasoning about strings in databases
Foundations of Databases
Introduction To Automata Theory, Languages, And Computation
Computers and Intractability
The AQUA Approach to Querying Lists and Trees in Object-Oriented Databases
Implementing a Declarative String Query Language with String Restructuring
Supporting Lists in a Data Model Timely Approach)

--CTR
Matti Nyknen , Esko Ukkonen, The exact path length problem, Journal of Algorithms, v.42 n.1, p.41-53, January 2002
Gsta Grahne , Raul Hakli , Matti Nyknen , Hellis Tamm , Esko Ukkonen, Design and implementation of a string database query language, Information Systems, v.28 n.4, p.311-337, June
transducers;finiteness dependencies;multi-tape automata