Some Results Concerning Two-Dimensional Turing Machines and Finite Automata ^{∗}

H.Petersen ^{†}

Institut für Informatik der Universität Stuttgart Breitwiesenstraße 20–22, D-70565 Stuttgart e-mail: petersen@informatik.uni-stuttgart.de

Abstract

We show that emptiness is decidable for three-way two-dimensional nondeterministic finite automata as well as the universe problem for the corresponding class of deterministic automata. Emptiness is undecidable for three-way (and even two-way) two-dimensional alternating finite automata over a single-letter alphabet. Consequently inclusion, equivalence, and disjointness for these automata are undecidable properties.

We establish a hierarchy result for space bounded two-dimensional alternating Turing machines above logarithm where the languages witnessing the hierarchy are over single-letter alphabets. Below logarithm we prove that an infinite hierarchy of languages over larger alphabets exists.

The results rely mainly on a translational technique from one to two dimensions. Using this technique we can also show some connections between open problems of two-dimensional automata theory and onedimensional complexity theory.

1 Introduction and Notation

We study problems arising in the theory of space bounded two-dimensional Turing machines and two-dimensional finite automata. We solve several of the open problems posed in the survey [4, 5] and link other problems to questions about one-dimensional automata.

For a very extensive bibliography as well as for the exact definitions of the models investigated we refer to [4, 5]. Note that the Turing machines are equipped with a two-dimensional rectangular read-only input tape and a onedimensional read-write work-tape. The input is bordered by special endmarkers.

We will denote the classes of one-dimensional languages accepted by s(n) space bounded deterministic, nondeterministic, and alternating Turing machines by DSPACE(s(n)), NSPACE(s(n)), and ASPACE(s(n)). For classes of twodimensional automata and languages we adopt the notation from [4, 5]. The classes of two-dimensional finite deterministic, nondeterministic, and alternating automata are denoted by DFA, NFA, and AFA. If the automata cannot move their head up they are called three-way which is denoted by a prefix ‘T’ (TDFA, TNFA, TAFA). Deterministic finite automata that have k markers or pebbles that they may put onto cells of their two-dimensional input and pick up later are called DMA(k).

∗The main part of this work was done at the University of Hamburg †Supported in part by ESPRIT Basic Research Action WG 6317: Algebraic and Syntactic Methods in Computer Science (ASMICS 2)

The two-dimensional Turing machines that we investigate operate on square input-tapes and form the classes DTM^{s}, NTM^{s}, and ATM^{s} (in [4, 5] rectangular input tapes are considered. This leads to a more complicated notation which will not be used here.)

We are interested in space bounds s(n) that map non-negative integers to positive integers, i.e. s(n) ≥ 1. The Turing machines operating in space bounded by s(n) where n is the number of rows resp. columns of the input are called DTM^{s}(s(n)), NTM^{s}(s(n)), and ATM^{s}(s(n)).

If X is some class of automata then L[X] is the class of languages accepted by these automata. We also consider the restriction of the automata in X to single-letter input alphabets. This will be denoted by X(0).

We write ‘⊂’ for proper inclusion.

2 Links Between One- and Two-Dimensional Machines

Throughout the paper we will need the following operation ρ mapping onedimensional words over an alphabet Σ to square tapes over Σ × Σ. Let w = a_{1}a_{2} ⋯ a_{n} be a word of length n. Then ρ(w) = z where z(i, j) = (a_{i}, a_{j}) for 1 ≤ i ≤ n and 1 ≤ j ≤ n. Thus a symbol of z in a certain row and column has the corresponding symbol of w in the first resp. second component. A word w = a_{1}a_{2} ⋯ a_{n} is mapped to

(a_{1}, a_{1})  (a_{1}, a_{2}) ⋯ (a_{1}, a_{n−1})  (a_{1}, a_{n})
(a_{2}, a_{1})  (a_{2}, a_{2}) ⋯ (a_{2}, a_{n−1})  (a_{2}, a_{n})
⋮  ⋮  ⋮  ⋮
(a_{n−1}, a_{1}) (a_{n−1}, a_{2}) ⋯ (a_{n−1}, a_{n−1}) (a_{n−1}, a_{n})
(a_{n}, a_{1})  (a_{n}, a_{2}) ⋯ (a_{n}, a_{n−1})  (a_{n}, a_{n})

This operation is extended in the usual way to languages. Note that for a singleletter alphabet Σ (|Σ| = 1) we have |Σ × Σ| = 1.

Lemma 1 A one-dimensional language L is accepted by an alternating two-way two-head finite automaton if and only if ρ(L) ∈ L[AFA].

Proof: The one-dimensional automaton simulates the two-dimensional device by storing the row and column in its head positions. It assembles the pair from the symbols read by the heads.

Conversely the two-dimensional automaton first checks that its input is a square by moving diagonally. In another universal branch it verifies that the first components of the input symbols within every row agree and that within every column the second components are identical. Note that this phase requires only down and right moves since the tests can be done in parallel.

Then the two-dimensional automaton starts a step by step simulation by storing one head-position as the current row number and the other position as the column number. The currently scanned symbols are available as the components of the symbol from Σ read by the head. □

Without modifying the simulation we get:

Lemma 2 A one-dimensional language L is accepted by an alternating one-way two-head finite automaton if and only if ρ(L) ∈ L[AFA] for a two-dimensional automaton that moves its head only down and to the right.

Lemma 3 A one-dimensional language L is accepted by a nondeterministic (deterministic) two-way two-head finite automaton if and only if ρ(L) ∈ L[NFA] (L[DFA]).

Proof: The simulations are the same as in the proof of Lemma 1. The only difference is that now the two-dimensional automaton sequentially checks that its input is of an appropriate form, i.e. is in ρ(Σ^{∗}). □

Lemma 4 Let s(n) ≥ log n be a space bound. A language L is in XSPACE(s(n)) if and only if ρ(L) ∈ L[XTM^{s}(s(n))] for X ∈ {A, N, D}.

Proof: The two-dimensional machine first checks (without using any storage) the form of its input as in the proof of Lemma 3. Then it ignores the first components and uses the first row as the input when simulating the one-dimensional machine.

For the reverse implication the one-dimensional machine allocates two areas of size O(log n) for storing a row and column position of the two-dimensional machine and simulates it step by step. □

We will now present some applications of the above operation.

Concerning problem (3) of Section 2.2 in [4, 5] asking if there is a set in L[NFA] not in L[DMA(1)] it is claimed in [14] that the problem is at least as hard as the question whether DSPACE(log n) = NSPACE(log n). While the arguments given that the answer “no” implies DSPACE(log n) = NSPACE(log n) are correct and we can even slightly strengthen this statement below, an answer “yes” does not tell us anything about the relation between DSPACE(log n) and NSPACE(log n). This is because it may happen that one marker is not sufficient for simulating every NFA. An analogous situation can be observed in the case of DFA and NFA where it is known that DFA cannot accept the set of those square tapes with an odd side length that have a certain central symbol while this is possible for NFA, see Theorem 4.3.4 in [12].

Theorem 1 If L[NFA] ⊆ ⋃_{k≥0} L[DMA(k)] then deterministic and nondeterministic logarithmic space bounded one-dimensional Turing machines are equivalent (DSPACE(log n) = NSPACE(log n)) and conversely.

Proof: The graph accessibility problem GAP is complete for NSPACE(log n). It is easy to see that GAP can be accepted by a nondeterministic two-way two-head finite automaton. Hence by Lemma 3 ρ(GAP) is in L[NFA]. It is clear that a DMA(k) working on a word from ρ(Σ^{∗}) can be simulated in logarithmic space which concludes the proof of the forward implication.

Now assume that DSPACE(log n) = NSPACE(log n). An NFA can be simulated by a nondeterministic one-dimensional Turing machine working in logarithmic space that receives the rows of the input tape separated by a special symbol. By the assumption this machine can be converted into a deterministic one which in turn is simulated by a one-dimensional marker automaton (see [15]). Finally the input can be replaced with a rectangular tape again. □

If the input alphabet is restricted to one letter we obtain a somewhat weaker result.

Theorem 2 If L[NFA(0)] ⊆ ⋃_{k≥0} L[DMA(k)] then deterministic and nondeterministic linear space bounded one-dimensional Turing machines are equivalent (DSPACE(n) = NSPACE(n)) and conversely.

Proof: In [9] it has been shown that DSPACE(n) = NSPACE(n) if and only if every language over a single-letter alphabet that can be accepted by a nondeterministic two-way one-counter automaton whose counter is bounded by the input length can be accepted by a deterministic logarithmic space bounded Turing machine. Such a counter automaton can be simulated on square inputs by Lemma 1 (obviously a head is at least as good as a counter). Conversely a Turing machine can within logarithmic space count the input length and then ignore its input tape. This latter computation can—assuming equality of the complexity classes–be done by a deterministic machine which is in turn simulated by a marker automaton. □

3 Decision Problems

We start with the positive solution of some open problems from Section 2.6 in [4, 5].

Theorem 3 The emptiness problem for nondeterministic three-way finite automata on two-dimensional tapes (TNFA) is decidable.

Proof: We effectively reduce the emptiness-problem for TNFA to the corresponding problem for TNFA(0). The latter is known to be decidable [3].

We recall from [13] that the behaviour of a deterministic two-way automaton entering a portion of tape can be thoroughly described by a mapping from states to states augmented by an element marking that the automaton will never leave this portion again. We will modify this concept in several ways. First we are dealing with nondeterministic automata. Therefore the mapping is to sets of states. Further other possibilities are to advance to the next row or accept the input (in [13] acceptance could only occur at the right border of the input).

Now we will describe how a TNFA M with k states is transformed into a TNFA(0) M′ such that M′ accepts an input tape of size n × m if and only if M accepts some input of the same size. Suppose M enters a row with the inscription wxy where x is the symbol on which M’s head rests. Then M may enter w in any of the k states and for every state there are k + 2 ways of continuing the computation. M may return to x in one of k states, accept, or go to the next row (we are not interested in rejecting or looping computations here). The total number of possible behaviours is 2^{(k+2)k}. Generalizing this one step further we consider all tapes of length i = |w| and obtain a set s_{i} describing all possibilities of maximum size 2^{2^{(k+2)k}}. Note that these values are independent of the actual input size. Now given a set associated to a length i = |w| it is clear that the set for i + 1 can be generated by considering all symbols that can be attached to some input of length i. This may even be done by a deterministic one-way automaton A_{L} operating on a unary string of length i + 1. The last property allows us to also compute s_{i−1} from s_{i} by using a technique due to Hopcroft and Ullman that is sketched in Lemma 4 of [2]. Essentially M′ starts a backward simulation of the deterministic automaton until either the state becomes unique or the endmarker is reached. Then the automaton is run forward until it returns to its old position.

In a totally symmetric way the right portion of the input y is handled by a deterministic automaton A_{R} that works from right to left.

Initially M′ determines the state that A_{R} is in by running it on the entire first row and resets A_{L} to its initial state. Then it simulates M by moving its head in one direction, updating A_{L} and A_{R}, guessing a sequence of input symbols and a sequence of matching crossing sequences compatible with the symbols as well as with the sets determined by A_{L} and A_{R} until it either reaches an accepting state of M or M goes to the next row. In the latter case the simulation continues in that row. For a computation without loops the length of the crossing sequences is bounded and therfore each sequence can be kept in the finite control of M′.

We note that M′ never visits a tape cell twice although M in its computation may do so. □

Corollary 1 The emptiness problem and the universe problem for deterministic three-way finite automata on two-dimensional tapes (TDFA) are decidable.

Proof: The first statement is immediate. The second claim follows from the effective complementation of TDFA given in Theorem 1 of [14]. □

The following result solves another problem from Section 2.6 in [4, 5].

Theorem 4 The emptiness problem for alternating three-way finite automata on two-dimensional tapes over a single-letter alphabet (TAFA(0)) is undecidable.

Proof: In [11] it is shown that the emptiness problem for one-way two-head alternating finite automata over single-letter alphabets is undecidable in the one-dimensional case. By Lemma 2 every one-dimensional automaton A can be transformed into a TAFA(0) B such that A accepts some word w if and only if b accepts ρ(w). This proves the theorem.

In order to make the method more transparent and prepare one of the corollaries we will briefly sketch the method in [11]. Essentially it consists of a reduction of the halting problem for two-counter automata to the emptiness problem. The counters are encoded by a single number that is stored as the distance of one of the heads to the right endmarker. The contents are stored as exponents of two primes, e.g. 2 and 3. Decrement is performed by dividing this number by the appropriate prime. Increment seems to be impossible since the head cannot move back. Therefore we initially multiply the number stored by a sufficiently large power of 5. Then a multiplication by 2 or 3 can be combined with a division by 5. As a result the head never has to move left. □

Note: In the above construction the head of the TAFA(0) never moves left. The result and the following corollaries therefore still hold for two-way automata with down and right movements only.

The emptiness problem above can be reduced to an inclusion resp. equivalence test with the empty set or disjointness with the set of all tapes over the given alphabet. Therefore the preceding result also solves those problems from [4, 5].

Corollary 2 For TAFA(0) inclusion, equivalence, and disjointness are undecidable.

In the proof from [11] sketched above no use was made of infinite computations. Hence it is possible to exchange accepting and rejecting states and obtain the

Corollary 3 The universe problem is undecidable for TAFA(0).

4 Hierarchy Results

From the translational technique of Lemma 4 for alternating Turing machines we get a hierarchy result analogous to Theorem 2.16 of [4, 5] searched for in the open problem of Section 2.4 of [4, 5].

Theorem 5 Let s_{2}(m) be a one-dimensionally space constructable function. Suppose s_{1}(m) ∈ o(s_{2}(m)) and s_{2}(m) ≥ log m. Then there exists a set in L[ATM^{s}(s_{2}(m))] but not in L[ATM^{s}(s_{1}(m))]

Proof: It is well-known that a corresponding space hierarchy exists for onedimensional machines, see e.g. Exercise 3.6.5 in [1]. By Lemma 4 we obtain the hierarchy for two-dimensional machines. □

Remark: Since the diagonal argument above can be based on the input length we obtain a hierarchy result for languages over single-letter alphabets if the bound s_{2} is fully two-dimensionally space constructable.

We recall the notion of strong and weak s(n) space bounded computations. In the weak mode of operation it is sufficient that one of the (possibly many) accepting computation trees of an alternating machine obeys the bound while no assumption is made concerning the rejected inputs. For the strong mode we require that every reachable configuration respects the bound.

The following result can be shown for nondeterministic, deterministic, and alternating machines (the constructability notion has to match the dimension of the input tape), see Theorem 8.1.1 in [15].

Fact 1 If a function s(n) is fully space constructable then weak and strong mode of acceptance coincide for s(n) space-bounded machines.

For two-dimensional Turing machines the following has been shown in [7]:

Fact 2 If s_{1}(n) is space constructable by a two-dimensional Turing, s_{1}(n) ≤ log n and s_{2}(n) = o(s_{1}(n)) then L[DTM^{s}(s_{1}(n))] \ L[ATM^{s}(s_{2}(n))] is nonempty if the strong mode of acceptance is assumed for the complexity classes.

A third important step is the full constructability on two-dimensional machines of a rich family of functions growing more slowly than log log n as shown in [10]. As a special case of this result we have

Fact 3 The following functions are fully constructable for all k ≥ 1:

f_{k}(n) = \{ \begin{matrix}log^{(k)}(\sqrt{n/4}) & if n = 2^{2m} for some m ≥ 0 \\ 1 & otherwise \end{matrix}

where log^{(k)} is the k-fold iteration of the logarithm.

These facts imply an infinite hierarchy of language classes for two-dimensional alternating Turing machines below log n analogous to Corollary 2.2 of [4, 5]:

Theorem 6 For any constant c > 0 and each k ≥ 1

L[AFA^{s}] = L[ATM^{s}(c)] ⊂ … ⊂ L[ATM^{s}(f_{k+1}] ⊂ L[ATM^{s}(f_{k})] ⊂ …

We summarize the hierarchy results for two-dimensional Turing machines

• Above log n the known hierarchies of the one-dimensional case can be transferred to two-dimensional machines with the help of the translational operation ρ (for deterministic and nondeterministic machines these hierarchies were known [4, 5]). The hierarchies are witnessed by languages over single-letter alphabets.

• Below log n the situation depends on the mode of operation:

– Deterministic machines with a strong space-bound can be transformed into halting ones by Sipser’s simulation (see e.g. [15]). As pointed out in [10] the full constructability of arbitrary slowly growing functions gives rise to a corresponding hierarchy of classes of languages over single-letter alphabets.

– For nondeterministic and alternating two-dimensional Turing machines we could show above that there are hierarchies of language classes provided that no restriction is imposed on the size of the alphabet.

Thus it remains open whether the hierarchies for nondeterministic and alternating machines can be based on single-letter alphabets. It would also be interesting to know if the notions of constructability and full constructability can be separated.

References

[1] J.Balcazár, J.Diáz, J.Gabárro: Structural Complexity II, Springer (1990).

[2] O.H.Ibarra, S.M.Kim, L.E.Rosier: Some characterizations of multihead finite automata, Inform. and Control 67 (1985) 114–125.

[3] K.Inoue, I.Takanami: A note on decision problems for three-way twodimensional finite automata, IPL 10 (1980) 245-248.

[4] K.Inoue, I.Takanami: A survey of two-dimensional automata theory, Proc. Machines, Languages, and Complexity (J.Dassow, J.Kelemen eds.), Springer LNCS 381 (1989) 72–91.

[5] K.Inoue, I.Takanami: A survey of two-dimensional automata theory, Inf. Sci. 55 (1991) 99–121.

[6] T.Jiang, O.H.Ibarra, H.Wang: Some results concerning 2-d on-line tesselation acceptors and 2-d alternating finite automata, Theor. Comput. Sci. 125 (1994) 243–257.

[7] T.Jiang, O.H.Ibarra, H.Wang, Q.Zheng: A hierarchy result for 2dimensional TM’s operating in small space, Inf. Sci. 64 (1992) 49–56.

[8] K.N.King: Alternating multihead finite automata, Theor. Comput. Sci. 61 (1988) 149–174.

[9] B.Monien: The LBA-problem and the deterministic tape complexity of twoway one-counter languages over a one-letter alphabet, Acta Informatica 8 (1977) 371–382.

[10] H.Petersen: On space functions fully constructed by two-dimensional Turing machines, IPL 54 (1995) 9–10.

[11] H.Petersen: Alternation in simple devices, Proc. ICALP95.

[12] A.Rosenfeld: Picture Languages, Academic Press, New York (1979).

[13] J.C.Shepherdson: The reduction of two-way automata to one-way automata, IBM Journal of Res. and Dev. April (1959) 198–200.

[14] A.Szepietowski: Some remarks on two-dimensional finite automata, Inf. Sci. 63 (1992) 183–189.

[15] A.Szepietowski: Turing machines with sublogarithmic space, Springer LNCS 843 (1994).