Alternation in Simple Devices ^{∗}

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 undecidable for alternating one-way twohead finite automata operating on unary input. This solves an open problem posed by Geidmanis. Further we show that a conjecture by King concerning the hierarchy of languages accepted by alternating one-way multihead finite automata does not hold. We also consider closure properties of the languages accepted by these devices and obtain as consequences that the Boolean closures of linear and general context-free languages are contained in the lower levels of the hierarchy. Some other simulation techniques are outlined.

1 Introduction

In this paper we will study alternation in a very restricted class of machines, alternating one-way multihead finite automata which were introduced and investigated by King [5]. For the formal definitions we refer to [5] and only recall that such automata move a finite number of heads on a read-only input tape which is bordered at the right by an endmarker. The finite control may contain universal states. If the automaton reaches such a state it accepts only if all successor configurations are accepting. We will denote the class of languages accepted by alternating one-way k-head finite automata by 1AFA(k). If we consider decision problems for these classes we tacitly assume that the languages are given by automata of the corresponding class and will denote the classes of automata by the abbreviation 1AFA(k).

One of the questions arising in the investigation of these devices is whether simple automata benefit from the ability to use alternation. We can show that the emptiness problem even for 1AFA(2) with unary input alphabets is undecidable. This problem is decidable for nondeterministic one-way multihead automata with unary alphabets and undecidable for deterministic two-head oneway finite automata with a binary input alphabet.

∗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)

Then we will show that a conjecture by King fails stating that a certain language over a unary alphabet is not contained in 1AFA(2). In the development we will exhibit some techniques for “programming” a 1AFA(2) that seem interesting in their own right.

An important topic concerning classes of formal languages are closure properties. We observe here that the classes 1AFA(k) are closed under complementation. Combining this property with inclusions previously shown we obtain rich classes of languages already contained in the lower levels of the hierarchy of languages accepted by these automata.

In the last section we describe a translational technique for these automata showing that a large number of heads can be simulated on a suitably modified input by a fixed and rather small number of heads.

A few remarks on notation: The automata receive an input w with a right endmarker. Therefore the input tape has |w| + 1 squares and h_{i}, the position of head i, is a number from 0 (initial position) to |w|. Often we will not use h_{i} but d_{i} = |w| − h_{i}, the distance of head i to the endmarker. Note that the initial distance of all heads is |w|.

2 Results

A useful property of 1AFA(k) has been shown in [5] and will be used throughout the paper.

Lemma 1 A 1AFA(k) which can detect coincidence of heads (the heads are sensing) can be simulated by a 1AFA(k) lacking this feature.

It is known that languages accepted by 1AFA(1) and 2AFA(1) are regular. King has shown that 1AFA(2) contains the nonregular unary language L_{1} = {0^{2^{n}} | n ≥ 2} while all unary languages accepted even by nondeterministic multihead pushdown automata are regular [4]. In those cases where the languages accepted are regular effective transformations of the devices into finite automata are given in the proofs and emptiness therefore is decidable. It is also known that emptiness is undecidable for deterministic one-way two-head automata over alphabets with at least two symbols, a result due to Greibach [7].

Geidmanis considered the emptiness problem of 1AFA(k) over unary alphabets and gave a proof that this problem is undecidable for k ≥ 3 [2, 3]. He posed as an open problem whether or not the emptiness problem for 1AFA(2) operating on unary input is decidable. Here we present the negative solution to this question which has a surprisingly elementary proof.

Theorem 1 The emptiness problem for 1AFA(2) operating on unary input is undecidable.

Proof: We describe a reduction of the halting problem for two-counter automata which are started with the input on one of their counters (the other counter is empty). By the universality of such machines [6] this problem is undecidable and undecidability of the given problem follows.

Let a two-counter automaton M and an input i be given. A 1AFA(2) A simulating M on i first universally checks that its input-length is divisible by 2^{i}, not divisible by 2^{i+1} and 3. The input length n can therefore be written as

n = 2^{i}3^{0}5^{s}r

where r ≥ 1 is not divisible by 2, 3 or 5. Now A starts a simulation of M. The factorization of the distance of the first head from the endmarker encodes both counters, where the exponent of 2 represents the first counter and the exponent of 3 the second. If M tests a counter for zero A universally branches to verify that the head distance is not divisible by 2 or 3. If M decrements one of the counters A uses its second head to divide d_{1} by 2 resp. 3. Both heads can be easily aligned afterwards by Lemma 1. If finally M increments a counter A multiplies the number stored by its first head by \frac{2}{5} resp. \frac{3}{5}. The distances of A’s heads are d_{1} and d_{2}. Then d_{2} = \frac{2}{5}d_{1} is equivalent to \frac{d_{2}}{2} = \frac{d_{1}}{5} . This condition can be universally verified by moving the second head two squares while moving the first head five times. The operation transforms d_{1} = 2^{a}3^{b}5^{c}r′ into d′_{1} = 2^{a+1}3^{b}5^{c−1}r′. The second counter of M is simulated similarly.

If A is able to complete the simulation of M it accepts its input, otherwise it rejects. If M halts with input i then A accepts every input of sufficient length and satisfying the conditions on divisibility, hence the language accepted is not empty (and even infinite due to the factor r). Conversely if M does not halt there will be no input which A accepts. The initial exponent s of 5 gives an upper bound on the number of increment operations that can be performed in the course of the simulation. Since it can be arbitrarily large a halting computation can be completed for sufficiently large s. □

On unary input a 1AFA(2) can be simulated by an alternating one-counter automaton. The latter automaton guesses the input length on its counter and universally verifies it. Then it simulates the 1AFA(2) in an obvious way. This shows

Corollary 1 The emptiness problem for alternating one-counter automata operating on unary input is undecidable even if the counter makes at most one reversal on every path of the computation.

By the usual arguments and the effective closure of 1AFA(2) under complementation (see below) we get

Corollary 2 Equivalence, finiteness, inclusion, disjointness, and universe problem are undecidable for 1AFA(2) as well as for alternating one-counter automata operating on unary input.

Similar results hold for alternating one-way two-tape automata.

One of the main open problems in the theory of alternating finite automata is whether k + 1 heads are better than k for one-way devices, i.e. the question whether 1AFA(k) ≠ 1AFA(k+1) for k ≥ 2 (for k = 1 the inequality is true because of L_{1}). For deterministic and nondeterministic automata this problem has been solved in [9], even for automata with sensing heads that can detect each others.

King [5, p. 161] defined the following family of languages:

L_{k} = {0^{2^{2^{...}^{2^{n}}}} | n ≥ 1}

where k is the number of 2’s in the exponent. King conjectured that L_{2} is not in 1AFA(2). This would separate the second and third level of the hierarchy since L_{k} ∈ 1AFA(3) for all k. We can however show that L_{2} ∈ 1AFA(2).

In the following we will be interested in distances of head-positions and introduce two values ℓ and r. The distance of the trailing head to the leading head of a 1AFA(2) will be denoted by ℓ = h_{1} − h_{2} = d_{2} − d_{1}. The distance d_{1} of the leading head to the (right) endmarker will be denoted by r. We write bin(n) for the binary representation of n without leading zeros.

Lemma 2 A 1AFA(2) can compare ℓ and r.

Proof: The 1AFA(2) moves the trailing head twice as fast as the leading head towards the endmarker. Depending on the head that reaches the endmarker first it determines the relation between ℓ and r. □

By adapting the “speed” of the heads it is also possible to compare multiples of ℓ and r.

Lemma 3 A 1AFA(2) can check bin(r) for membership in a fixed regular set.

Proof: The 1AFA(2) moves the trailing head onto the position of the leading head (Lemma 1), guesses if r is even or odd, if it guessed odd advances both heads, moves one of the heads to the central square (which is universally verified by Lemma 1) and repeats this process with the new r until all relevant digits have been processed. All guesses are fed into a finite automaton simulated in the finite control of the 1AFA(2). □

Lemma 4 If r ≥ ℓ then a 1AFA(2) can check bin(ℓ) for membership in a fixed regular set.

Proof: Move both heads in parallel until ℓ = r (Lemma 2), then check r (Lemma 3). □

Theorem 2 The language L_{2} is in 1AFA(2) .

Proof: The 1AFA(2) accepting L_{2} first verifies that the input is of the form 0^{2^{m}} for some m ≥ 2, if m = 2 it immediately accepts. Then it moves one head to such a position that ℓ ≤ r and bin(r) ∈ 100^{∗}1^{∗} and advances its second head to the same position. Then it repeats the following steps:

• If bin(r) = 1011 then accept.

• If bin(r) ∉ 10{1, 0}^{∗} \ 10^{∗} = 10{1, 0}^{∗}1{1, 0}^{∗} then reject.

• Move one of the heads to a position such that the new r′ and ℓ′ satisfy bin(ℓ′) ∈ 10^{∗} (ℓ′ is a power of 2) and ℓ′ ≤ r′ ≤ 2ℓ′.

• Move the trailing to the position of the leading head and then both one step.

All of the operations on the heads are possible by the preceding lemmas.

The above algorithm transforms a distance 2^{p} + q (where q < 2^{p−1}) into 2^{p−1} + (q − 1). Since it starts with 2^{m−1} + 2^{r} − 1 and terminates with 2^{3} + 3 it correctly verifies that m = 2^{r} for some r ≥ 1. □

By using the algorithm recursively it is possible to show that L_{k} ∈ 1AFA(2) for every k.

Next we will consider closure properties of the classes 1AFA(k). It has been remarked in [1] that the complements of languages accepted by nondeterministic one-way k-head finite automata are in 1AFA(k) (in fact the 1AFA(k) possess universal states only). Here we generalize this statement.

Lemma 5 For every 1AFA(k) A there is an equivalent automaton A′ that has no infinite computation tree. Further all leaves of computation trees are configurations with all heads on the endmarker.

Proof: Since the movement of heads is unidirectional the only way a path in the computation tree extends to infinity is by repeating a state in the finite control while the heads remain stationary. We will show how to rule out such behaviour.

Let A have the set of states S and introduce as states for A′ all pairs from S × {1, … |S|}. Whenever there is a transition in A from state s_{1} to s_{2} moving a head we let all transitions from (s_{1}, i) to (s_{2}, 1) for 1 ≤ i ≤ |S| be transitions of A′. If there is a transition from s_{1} to s_{2} which does not move a head there are transitions from (s_{1}, i) to (s_{2}, i + 1) for 1 ≤ i ≤ |S| − 1 in A′. We will indicate why A and A′ are equivalent. Acceptance of 1AFA(k) is defined using a finite accepting computation tree and such a tree can be reduced such that no configuration repeats on a path [5]. In the case of A this means that after at most |S| steps a head moves. Such a reduced tree can clearly be transformed into an accepting tree for A′ by counting the stationary moves in the second component of its states. Conversely an accepting computation tree of A′ is simply transformed into a tree of A by projection on the first component of each state.

Now we outline how to modify the automaton such that it has as leaves only configurations with all heads on the endmarker. If there is an accepting state which allows further transitions we introduce a state which existentially chooses between two copies of the old state, one of which accepts and allows no further transition, and another which is identical to the old one but non-accepting. Then we make all blocking states (for certain input symbols other than the endmarker no transition is possible) non-accepting and add transitions to new states which simply advance all heads and either accept or reject according to the original decision. □

Theorem 3 The classes 1AFA(k) are closed under complement and consequently they are closed under Boolean operations.

Proof: By Lemma 5 we can assume that all computation trees of the automata are finite and in normalized form. To obtain an automaton accepting the complement we exchange the role of accepting/nonaccepting blocking states and the role of universal/existential states. By induction on the depth of the (partial) computation trees we have that every accepting configuration becomes rejecting and vice versa. □

In [5] it has been shown that 1AFA(3) contains the context-free languages and 1AFA(2) contains the linear context-free languages. We therefore get

Corollary 3 1AFA(3) and 1AFA(2) contain the Boolean closures of contextfree and linear context-free languages resp.

Since 1NFA(k) are restricted 1AFA(k) we also have

Corollary 4 The Boolean closure of 1NFA(k) is contained in 1AFA(k) . The containment is proper for k ≥ 2.

Properness follows from the fact that languages accepted by 1NFA(k) with a unary input alphabet are regular [4] while L_{1} ∈ 1AFA(2).

It is interesting to compare this “efficiency” in terms of heads required for Boolean operations with automata lacking alternation. Consider two languages L_{i} and L_{j} recognized by one-way finite automata with i and j heads. If the automata are deterministic then L_{i}∩L_{j} and L_{i}∪L_{j} can be accepted by automata with i + j − 1 heads [7, Remark 4, p. 392]. Further the complements can be recognized by devices of the same type.

If the automata are nondeterministic then the parallel simulation from [7] gives i + j − 1 heads for L_{i} ∩ L_{j} while max(i, j) clearly suffices for L_{i} ∪ L_{j}. No increase in the number of heads will in general give an automaton recognizing the complement of L_{i} or L_{j} as follows from [9].

By the preceding result alternation allows us to perform all these operations on languages from 1AFA(k) without leaving the class.

As a last point we will briefly sketch how a one-way finite automaton can use alternation for simulating certain aspects of two-way automata. By leaving one head stationary on the first symbol such an automaton can simulate heads that move from right to left by guessing the symbol under a head and universally verifying it with the help of the head on the first symbol. By generalizing the simulation of linear context-free grammars it is also possible to simulate pairs of heads starting at both ends of the input and meeting somewhere inside the word. As a further example of the power of alternation we can show a translational result that in a similar way holds for various two-way automata. Let T_{k} for k ≥ 1 be the following operation on words [8, p. 226]:

T_{k}(w) = w^{|w|^{k−1}}

Then we have

Theorem 4 If L ∈ 1AFA(k) then T_{k}(L) ∈ 1AFA(4) .

Proof: At several places in this proof we have to divide the distance d_{j} of some head j to the endmarker by a number n stored as the distance of head 1 to the endmarker. This can be achieved with the help of two other auxiliary heads by placing one of them nondeterministically at a distance of d_{j}/n and then branching universally to align this head with head j and continue the computation or check the guess. The latter is done by placing the second auxiliary head n positions to the right of head j and then align them while moving the first auxiliary head one position. This is repeated until both heads reach the endmarker.

Let L be accepted by 1AFA(k) M. We will describe a 1AFA(4) M′ that on input T_{k}(w) simulates M on w. We note that |T_{k}(w)| = |w|^{k} and M′ first guesses |w| as the distance d_{1} of its head 1 to the endmarker. M′ can check it with the help of the three other heads by dividing the input length by this distance k times as described above. After guessing |w| M′ with heads 2 and 3 verifies that the input is a repetition of w. In another universal branch the simulation is initiated. The position h_{i} of head i of M is stored as h_{i} · |w|^{i−1} in head position h′_{2} of M′ that holds the sum of all these encodings (here 0 ≤ h_{i} ≤ |w| − 1, if a head reaches the endmarker it is stored in the finite control). If head i of M moves right M′ moves its second head |w|^{i−1} squares. For this purpose M′ guesses ⌊|w|^{i−1}/2⌋ as the distance of heads 3 and 4 where head 3 is aligned with head 2 and head 4 is placed to the right of heads 2 and 3. Then M′ universally either adds this distance twice to the position of head 2 (as well as the remainder of the division) or verifies that the distance is ⌊|w|^{i−1}/2⌋. This can be done by the division method and the observation that there is sufficient space to the right of head 4.

The symbol under head i of M can be determined by dividing d′_{2} − 1 (the distance to the endmarker minus 1) by |w|^{i−1} which can be done in a universal branch. By repeated subtraction of |w| M′ can also observe whether head i is on the last symbol and thus keep h_{i} ≤ |w| − 1. For these last operations M′ temporarily ignores the endmarker and thus transforms d′_{2} into d′_{2} − 1 (without moving head 2). We have

d′_{2} − 1 = |w|^{k} − 1 − ∑_{i=1}^{k} h_{i} · |w|^{(i−1)}

= (|w| − 1) · ∑_{i=0}^{k−1} |w|^{i} − ∑_{i=1}^{k} h_{i} · |w|^{(i−1)}

= ∑_{i=1}^{k}(|w| − h_{i} − 1) · |w|^{(i−1)}

= ∑_{i=1}^{k}(d_{i} − 1) · |w|^{(i−1)}

which shows that the correct distance is computed. □

It is remarkable that the previous translation is independent of the size of the alphabet and even works for unary languages.

3 Discussion

We have demonstrated the power of alternation in a very simple model of computation. Some open problems still remain:

• Do additional heads increase the power of one-way alternating finite automata?

• What is the relation of these automata to the two-way variety?

• Are there natural examples of languages not accepted by one-way alternating finite automata?

Acknowledgement: The author is indebted to K.N.King for help and encouragement.

References

[1] M.Ya.Alberts: Possibilities of various types of alternating automata, Cybernetics 6 (1986) (translated from Russian) 714–720.

[2] D.Geidmanis: On possibilities of one-way synchronized and alternating automata, Proc. MFCS 1990 (B.Rovan ed.) LNCS 452, 292–299.

[3] D.Geidmanis: Unsolvability of the emptiness problem for alternating 1-way multi-head and multi-tape finite automata over single-letter alphabet, Computers and Art. Int. 10 (1991) 133–141.

[4] M.A.Harrison, O.H.Ibarra: Multitape and multihead pushdown automata, Inf. Contr. 13 (1968) 433–470.

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

[6] M.L.Minsky: Recursive unsolvability of Post’s problem of “tag” and other topics in theory of Turing machines, Annals of Mathematics, 74, 3 (1961), 437–455.

[7] A.L.Rosenberg: On multi-head finite automata, IBM Journal Res. and Dev. 10 (1966) 388–394.

[8] K.Wagner, G.Wechsung: Computational Complexity, Reidel, Dordrecht (1986).

[9] A.C.Yao, R.L.Rivest: k + 1 heads are better than k, JACM 25 (1978) 337–