Martin Kutrib

Andreas Malcher

Carlo Mereghetti
email: carlo.mereghetti@unimi.it

Beatrice Palano
email: palano@unimi.it

Descriptional Complexity of Iterated Uniform Finite-State Transducers

Keywords: Iterated transducers, State complexity, Sweep complexity, Decidability

We introduce the deterministic computational model of an iterated uniform finite-state transducer ( iufst). A iufst performs the same length-preserving transduction on several left-to-right sweeps. The first sweep takes place on the input string, while any other sweep processes the output of the previous one. The iufst accepts or rejects upon halting in an accepting or rejecting state along its sweeps. First, we focus on constant sweep bounded iufsts. We study their descriptional power vs. deterministic finite automata, and the state cost of implementing language operations. Then, we focus on non-constant sweep bounded iufsts, showing a nonregular language hierarchy depending on sweep complexity. The hardness of some classical decision problems on constant sweep bounded iufsts is also investigated.

Introduction

Finite-state transducers are finite automata with an output and they have been studied at least since 1950s. A typical application of finite-state transducers is, for example, the lexical analysis of a computer program or an XML document. Here, the correct formatting of the input is verified, comments are removed, the correct spelling of the commands is checked, and the sequence of input symbols is translated into a list of tokens. The output produced is subsequently processed by a pushdown automaton that realizes the syntactic analysis. Another example is the use of cascading finite-state transducers. Here, one has a finite number of transducers T 1 , T 2 , . . . , T n , where the output of T i is the input for the next transducer T i+1 . Such cascades of finite-state transducers have been used, for example, in [START_REF] Friburger | Finite-state transducer cascades to extract named entities in texts[END_REF] to extract information from natural language texts. On the other hand, the Krohn-Rhodes decomposition theorem shows that every regular language can be represented as the cascade of several finite-state transducers each of which having a "simple" algebraic structure [START_REF] Ginzburg | Algebraic theory of automata[END_REF][START_REF] Hartmanis | Algebraic structure theory of sequential machines[END_REF]. Cascades of deterministic pushdown transducers are investigated in [START_REF] Citrini | On deterministic multi-pass analysis[END_REF] and it is shown that a proper infinite hierarchy in between the deterministic context-free and deterministic context-sensitive languages exists with respect to the number of transducers applied. All the examples considered so far have in common that the subsequently applied transducers are, at least in principal, different transducers. Another point of view is taken in [START_REF] Bordihn | Iterated sequential transducers as language generating devices[END_REF][START_REF] Manca | On the generative power of iterated transductions[END_REF], where subsequently applied identical transducers are studied. Such iterated finite-state transducers are considered as language generating devices starting with some symbol in the initial state of the transducer, iteratively applying in multiple sweeps the transducer to the output produced so far, and eventually halting in an accepting state of the transducer after a last sweep. These iterated finite-state transducers are quite powerful, since in the nondeterministic case non-recursive languages can be generated where the underlying transducer comprises of three states. Even in the deterministic case, one state suffices to generate the class of D0L Lindenmayer systems and two states are sufficient to generate languages which are neither context-free nor in 0L. It is an essential feature that the underlying finite-state transducer is not length-preserving. Several restrictions on finite-state transducers are studied in [START_REF] Pierce | Decision Problems on Iterated Length-Preserving Transducers[END_REF] with respect to the question of whether the (arbitrary) iteration of the restricted transducers is still computationally universal.

In this paper, we will consider iterated finite-state transducers as language accepting devices. In addition, to have a simple device, the underlying transducer is considered to be a Mealy machine [START_REF] Mealy | A method for synthesizing sequential circuits[END_REF], that is, a deterministic length-preserving device where each input symbol is translated according to its transition function into an output symbol. To be more precise, an iterated uniform finite-state transducer (iufst) works in several sweeps on a tape which is initially the input concatenated with a right endmarker. In every sweep the finite-state transducer starts in its initial state at the first tape cell, is applied to the tape, and prints its output on the tape. The input is accepted or rejected, if the transducer halts in an accepting or rejecting state.

We start our investigations of such devices having a fixed number k ≥ 1 of sweeps. Since in this case the language accepted by a k-iufst is always a regular language, it is of interest to compare such devices with deterministic finite automata (dfa) by investigating their descriptional complexity and the state cost of implementing language operations. General information on descriptional complexity can be found in the survey [START_REF] Holzer | Descriptional complexity -An introductory survey[END_REF] and many results on the operational state complexity are surveyed in [START_REF] Gao | A survey on operational state complexity[END_REF]. In addition, the NL-completeness of commonly considered decision problems on k-iufsts is pointed out.

We will also consider the case when the number of sweeps is not bounded by a fixed finite number. In this case, the resulting iufsts can be considered as restricted variants of one-tape Turing machines that iteratively sweep from left to right, starting at the first tape cell always in their initial state. It turns out that such devices can accept non-regular languages as soon as the number of sweeps is at least the logarithm of the length of the input. Moreover, there is a hierarchy depending on the number of sweeps and all commonly studied decidability questions turn out to be not even semidecidable.

The paper is organized as follows. In Section 2, we present the model of iufsts, and provide an example of a language accepted by a constant sweep bounded iufst, with a number of states which is exponentially smaller than that of any equivalent dfa. In Section 3, we focus on the descriptional power of constant sweep bounded iufsts (k-iufsts), providing example of languages where iterated transduction either helps or does not help in reducing the number of states of equivalent dfas. Section 4 is first devoted to study the optimal state cost of simulations between k-iufsts and dfas. Next, the impact on the number of states is studied, of modifying the number of sweeps on k-iufsts. The optimal state cost of implementing Boolean language operations and reversal on k-iufsts is investigated, and finally the NL-completeness of typical decision problems on k-iufsts is proved. In Section 5, we consider non-constant sweep bounded iufsts. First, we prove that o(lg n) sweep bounded iufsts accept regular languages only, and show that such a logarithmic sweep lower bound is tight for nonregular acceptance. Next, we exhibit a nonregular language hierarchy with respect to sweep complexity.

Definitions and Preliminaries

We denote the set of positive integers and zero {0, 1, 2, ...} by N. The reversal of a word w is denoted by w R , and for the length of w we write |w|. The reversal of a language L ⊆ Σ * is denoted by L R , its complement by L. By lg n we denote the logarithm of n to base 2. Throughout the article two devices are said to be equivalent if and only if they accept the same language.

An iterated uniform finite-state transducer is basically a deterministic finitestate transducer which processes the input in multiple passes (also sweeps). In the first pass it reads the input word followed by an endmarker and emits an output word. In the following passes it reads the output word of the previous pass and emits a new output word. It can be seen as a restricted variant of a one-tape Turing machine. The number of passes taken, the sweep complexity, is given as a function of the length of the input. Since here we are interested in weak preprocessing devices, we will consider length-preserving deterministic finite-state transducers, also known as Mealy machines.

Formally, we define an iterated uniform finite-state transducer (iufst) as a system T = Q, Σ, ∆, q 0 , , δ, F + , F -, where Q is the set of internal states, Σ is the set of input symbols, ∆ is the set of output symbols, q 0 is the initial state, ∈ ∆\Σ is the endmarker, F + ⊆ Q is the set of accepting states, F -⊆ (Q\F + ) is the set of rejecting states, and δ : Q×(Σ∪∆) → Q×∆ is the transition function, which is total on (Q \ (F + ∪ F -)) × (Σ ∪ ∆) and where the endmarker is emitted only if it is read, i.e., there are no transitions δ(p, x) = (q, ) with x = . The iufst halts when the transition function is undefined (which may happen only for states from F + ∪ F -) or if it enters an accepting or rejecting state at the end of a sweep. Since the transducer is applied in multiple passes, i.e., in any but the initial pass it operates on the output of the previous pass, the transition function depends on input symbols from Σ ∪ ∆. Let v ∈ ∆ * be the output produced by T on input w ∈ (Σ ∪ ∆) * in a complete sweep. Then we denote v by T (w). A word w ∈ Σ * is accepted by an iufst T if there is an r ≥ 1 such that w 1 = T (w ), w i+1 = T (w i ), 1 ≤ i < r, and the transducer T halts on w r in an accepting state. That is, the initial input is a word over the input alphabet Σ followed by the endmarker, and the output computed after r -1 iterations drives T in a final sweep where it halts in an accepting state. Similarly, an input w ∈ Σ * is rejected by T if there is an r ≥ 1 such that T halts in the final sweep on w r-1 in a rejecting state. Note that the output of the last sweep is not used. The language accepted by T is

L(T ) = { w ∈ Σ * | w is accepted by T }.
Let s : N → N be a function. If any word of length n is accepted or rejected in at most s(n) sweeps, the iufst is said to be of sweep complexity s(n). In this case, we use the notation s(n)-iufst.

In order to clarify this notion we continue with an example.

Example 1. For k ≥ 1, we consider the language E k = {a, b} * b{a, b} k-1 , whose words are characterized by having the letter b at the kth position from the right. Any deterministic finite automaton (dfa) needs at least 2 k states to accept

E k . The following k-iufst T = Q, Σ, ∆, q a , 0 , δ, F + , F -accepts E k with 3 states only. Set Q = {q a , q b , q -}, Σ = {a, b}, ∆ = {a, b, 0 , 1 , . . . , k-1 }, F + = {q b }, F -= {q -},
and specify the transition function as:

(1) δ(q a , a) = (q a , a)

(2) δ(q a , b) = (q b , a) (3) δ(q a , i ) = (q a , i+1 ), for 0 ≤ i ≤ k -2 (4) δ(q a , k-1 ) = (q -, k-1 ) (5) δ(q b , a) = (q a , b) (6) δ(q b , b) = (q b , b) (7) δ(q b , i ) = (q a , i+1 ), for 0 ≤ i ≤ k -2 (8) δ(q b , k-1 ) = (q b , k-1 )
The basic idea of the construction is to shift symbol by symbol the input word to the right (states q a and q b ), whereby an a is inserted at the first position and the last symbol is removed. In this way, in the first k -1 sweeps the input is shifted k -1 positions to the right. Now it is sufficient to check whether the last symbol is a b which is done in the last sweep. The number of the current sweep is given by the index of the endmarker.

Iterated Transductions vs. DFAs

As seen in Example 1, iterated transduction may lead to dramatically decrease the number of states for accepting regular languages. Here, we propose another family of languages showing the high descriptional power of k-iufst. For any integer k ≥ 2, we define the language

B k = { b 1 #b 2 # • • • #b m | b i ∈ {0, 1} k , m > 1, ∃i < m : b i = b m }.
For recognizing B k on a dfa, 2 2 k +1 states are necessary and sufficient. Instead: Theorem 2. For any k ≥ 2, the language B k can be recognized by a 2 k -iufst with 2 k (k + 4) states.

Proof. We informally explain the behaviour of a 2 k -iufst T for B k . At the first sweep, T stores the first block b 1 and "erase" any other occurrence of b 1 # by replacing it with b 1 # d . In case b 1 = b m , T accepts, otherwise it rewrites by 1 to store the sweep number, and continues. At the ith sweep, T searches a nonerased block to store, erases the occurrences of the stored block along the string, and matches it against b m . If the stored block matches b m , T accepts, otherwise it rewrites i-1 with i to record the sweep number, and continues. Clearly, within 2 k sweeps, T correctly accepts or rejects the input string. The number of states of T is as follows: 2 k+1 -1 to store a block not yet checked in previous sweeps, plus 2 k (k + 2) states to perform matching with every subsequent block along the string and to fix the outcome of matching, plus 1 state to continue the computation when, by reading the endmarker, T realizes it is not the last sweep. So, the total number of states is 2

k+1 -1 + 2 k (k + 2) + 1 = 2 k (k + 4).
However, some languages are so hard that even iterated transduction cannot reduce the size for their recognition. We are going to present a family of unary languages for which using k-iufst does not help in reducing the number of states of equivalent dfas. Let p be any prime number. We define

L p = { a m•p | m ≥ 0 }. Theorem 3. Let k ≥ 1.
Then p states are necessary and sufficient for a k-iufst to accept L p .

Proof. For the upper bound, consider the minimal dfa A for L p , which has exactly p states. The dfa A can be turned into a p-state k-iufst, as explained in Lemma 6 below.

For the lower bound, suppose by contradiction there exists a k-iufst T accepting L p with x < p states. Consider an input string a m•p , for m large enough, accepted by T at the endmarker after exactly k sweeps (these acceptance requirements can be assumed without loss of generality).

Since the input is unary, in the first sweep T runs into a cycle of length, say c 1 . Let β 1 be the output produced while running through one cycle. Then the input a m•p is rewritten as

α 1,1 β * 1 γ 1,1 with |β 1 | = c 1 = x 1 ≤
x < p, such that T enters and exits the cycle on β 1 in the same state. In the second sweep, T eventually runs into a cycle of length, say c 2 , on processing β * 1 . Since

|β 1 | = x 1 , we derive c 2 = x 2 • x 1 , for some x 2 ≤ x < p. Let β 2 be the output produced while running through one cycle. Then T rewrites β * 1 as α 2,1 β * 2 γ 2,1 with |β 2 | = x 2 •
x 1 , and the current string after the second sweep has the form α 1,2 α 2,1 β * 2 γ 2,1 γ 1,2 . This process continues until the kth sweep, where T eventually runs into a cycle of length, say c k , on processing

β * k-1 . Since |β k-1 | = x k-1 • x k-2 • • • x 1 , we derive c k = x k • x k-1 • • • x 1 , for some x k ≤ x < p. Let β k be the output produced while running through one cycle. Then T rewrites β * k-1 as α k,1 β * k γ k,1 with |β k | = x k • x k-1 • • • x 1
and the current string w after the kth sweep has the form

α 1,k α 2,k-1 • • • α k,1 β k γ k,1 • • • γ 2,k-1 γ 1,k ,
for some ≥ 1. Since the string w is accepted by T at the end of the kth sweep, also the string α

1,k α 2,k-1 • • • α k,1 β -1 k γ k,1 • • • γ 2,k-1 γ 1,k is accepted by T at the end of the kth sweep. But |α 1,k α 2,k-1 • • • α k,1 β -1 k γ k,1 • • • γ 2,k-1 γ 1,k | = m • p -|β k | = m • p -c k . Since c k = x k • x k-1 • • • x 1
and the x i are all less than p, and p is prime, m • p -c k cannot be a multiple of p. This means that T accepts a string not in L p , a contradiction.

Descriptional Complexity

In this section, we approach in a more general way the study of the descriptional power of k-iufst vs. dfas by providing general simulations between the two models. First, we consider the cost of turning a k-iufst into an equivalent dfa: Lemma 4. Let k > 0 be an integer. Every n-state k-iufst can be converted to an equivalent dfa with at most n k states.

The result presented in Lemma 4 turns out to be optimal. Lemma 5. There exists a family {L n,k } n,k>0 of unary languages such that each language L n,k is accepted by an n-state k-iufst, whereas any equivalent dfa needs at least n k states.

Proof. For any n, k > 0, we define

L n,k = { a c•n k | c ≥ 0 }.
The k-iufst T = Q, Σ, ∆, q 1 , 0 , δ, F + , F -accepts L n,k with n states only. We set Q = {q 1 , q 2 , . . . , q n }, Σ = {a}, ∆ = {a, 1, 2, . . . , n, n, 0 , 1 , . . . , k-1 }, F + = {q n }, F -= {q 2 , . . . , q n-1 }, and specify the transition function as:

(1) δ(q i , σ) = (q i+1 , i) if σ ∈ {a, n}

(q i , i) if σ ∈ {1, 2, . . . , n -1, n} for 1 ≤ i ≤ n -1 (2) δ(q n , σ) =    (q 1 , n) if σ ∈ {a, n} (q n , n) if σ ∈ {1, 2, . . . , n -1, n} (q 2 , σ) if σ ∈ { 0 , 1 , . . . , k-1 } (3) δ(q 1 , i ) = (q 1 , i+1 ) for 0 ≤ i ≤ k -2 (4) δ(q 1 , k-1 ) = (q n , k-1 )
The basic idea is that, along the first sweep, T checks whether the length of the input string is a multiple of n by rewriting it as a sequence of consecutive blocks of the form "12 • • • n", followed by 1 . For the second sweep, T checks whether the length of the input string is a multiple of n 2 by rewriting n consecutive blocks "12 • • • n" with the block "1 n 2 n • • • (n -1) n nn-1 n", followed by 2 . For the third sweep, T checks whether the length of the input string is a multiple of n 3 by rewriting n consecutive blocks "1 n 2 n • • • (n -1) n nn-1 n" with the block "1 n 2 2 n 2 • • • (n -1) n 2 nn 2 -1 n", followed by 3 . Clearly, by Transition (4), the input string can be accepted after the kth sweep only upon reading k-1 . In this case, the length of the input is easily seen to be a multiple of n k .

The fact that n k states are necessary for a dfa to accept L n,k follows from a trivial pumping argument.

Let us now focus on the opposite simulation, that is, dfas by k-iufst. Lemma 6. For n ≥ 3, every n-state dfa can be converted into an equivalent n-state k-iufst, with k ≥ 1. Lemma 6 is stated for at least three states. For dfas with less than three states, we can choose either to maintain the same number of states and perform one sweep only, or to add a new state and perform k sweeps.

One may expect that the size of a k-iufst may always be decreased by increasing the number of sweeps. However by Theorem 3, the construction provided by Lemma 6 is optimal.

States versus Sweeps

Here we turn to study the impact of modifying the number of sweeps on the size of iterated transducers. The possibility of trading states for input sweeps and vice versa has been investigated in the literature for several models of computations (see, e.g., [START_REF] Malcher | Descriptional complexity of two-way pushdown automata with restricted head reversals[END_REF]). Let us start with a simple observation on the minimal number of states necessary to establish a sweep complexity of at least two. Lemma 7. Let k ≥ 2 be an integer and T be some k-iufst with input alphabet Σ. Unless T accepts the trivial languages ∅ or Σ * , it has at least three states.

Proof. Let L(T ) be non-trivial. Then there are inputs that have to be accepted as well as inputs that have to be rejected. To this end, two states are necessary. On the other hand, T must not be in one of these two states at the end of the first sweep. Otherwise it would halt and could not start the second sweep. So, an additional state is necessary.

Concerning the relations between the necessary number of states and the number of sweeps we have the following situation: Theorem 3 shows that there are languages for which additional sweeps do not help to decrease the number of states at all. By Lemma 4, any n-state k-iufst can be converted into an equivalent dfa with at most n k states. Conversely, due to Lemma 7 we cannot reduce the number of states below three by increasing the number of sweeps. So, there is an upper bound for the number of sweeps that may help. In other words, for any regular language L we have a fixed sweep range from 1 to some k L in which we can trade states for sweeps and vice versa. For example, the sweep range for language L p of Theorem 3 is given by k Lp = 1, that is, it is just one sweep. In general, the next theorem gives a lower bound for the number of necessary states when one sweep is omitted. Theorem 8. Let k ≥ 2 and n ≥ 3 be integers, and T be an n-state k-iufst such that the minimal dfa for L(T ) has n k states. Then any (k -1)-iufst for L(T ) must have at least n k/k-1 states.

Proof. Assume a (k-1)-iufst T for L(T ) with strictly less than n k/k-1 states. If n k/k-1 is an integer, this means at most n k/k-1 -1 states. So, by Lemma 4, we could construct from T a dfa for L(T ) with at most (n k/k-1 -1) k-1 < n k states, a contradiction. Similarly, if n k/k-1 is not an integer, we have at most n k/k-1 states. Again, by Lemma 4, we could construct a dfa accepting L(T ) with ( n k/k-1 ) k-1 < n k states, a contradiction.

Example 9. For k ≥ 2 and n ≥ 3, let us consider the language L n,k of Lemma 5, where an n-state k-iufst accepting L n,k is constructed. Moreover, we noticed that the minimal dfa for L n,k has n k states. So, any (k -1)-iufst T accepting L n,k has at least n k/k-1 states.

Theorem 8 shows that omitting one sweep in the sweep range may increase the number of necessary states. However, once we have this increased number of states, the next question is whether this number of states can be used to decrease the number of sweeps furthermore for free. For example, assume that we have a 3-state 16-iufst. Then Theorem 8 says that any equivalent 15-iufst needs at least 4 states. However, since 4 14 is still greater than 3 16 , four states could be enough to reduce the number of sweeps by two. The next theorem provides a gradual reduction of the number of sweeps and the necessary states exemplarily for the language E k = {a, b} * b{a, b} k-1 of Example 1.

Theorem 10. Let ≥ 1 and k = 2 be integers. Then the useful sweep range for language E k is from 1 to 2 . Moreover, for any i ∈ {0, 1, . . . , -1} there is a 2 i -iufst accepting E k with 2 2 -i states, and for i = there is a 2 i -iufst accepting E k with 3 states.

Proof. For i = 0 the assertion follows since, in this case, we have a one-sweep iufst which needs as many states as a dfa to accept E k , i.e., 2 2 states as claimed. For i = , the assertion follows immediately from the construction of Example 1. For the remaining cases we modify the construction of Example 1 as follows. Instead of shifting the input k times by one position to the right, now we shift it 2 i times by 2 -i positions to the right. Since 2 i • 2 -i = 2 = k, altogether it is shifted again k positions to the right, so the construction does it. To shift the input by 2 -i positions, 2 2 -i states are necessary. For i = , Lemma 7 gives the lower bound of three states, where one state is needed to start a new sweep. For i < , there are enough states to be used to this purpose, i.e., that are neither accepting nor rejecting and can be entered upon reading the endmarker.

The State Cost of Language Operations on k-IUFSTs

As naturally done for many models of computation accepting regular languages (see, e.g., [START_REF] Bednárová | The size-cost of Boolean operations on constant height deterministic pushdown automata[END_REF]), we now analyze the state complexity of language operations on k-iufsts. To this aim, we asssume that their transition functions are always defined, so that acceptance/rejection takes place on the endmarker only, at the jth sweep, for some 1 ≤ j ≤ k. If not, transition functions can be easily completed by adding at most two states where we maintain the accept or reject outcome obtained in the middle of the input, while reaching the endmarker.

Let us start with Boolean operations. The first we consider is intersection:

Theorem 11. Let m, n, k ≥ 1 be integers, T 1 be an m-state k-iufst and T 2 be an n-state k-iufst. Then m • n states are sufficient for a k-iufst to accept L(T 1 ) ∩ L(T 2 ).

The cost of implementing intersection given in Theorem 11 is optimal, as proved in the following Theorem 12. Let k ≥ 1 be an integer. There exist infinitely many integers m, n > 1 such that an m-state k-iufst T 1 and an n-state k-iufst T 2 can be built, for which m • n states are necessary to accept L(T 1 ) ∩ L(T 2 ) on a k-iufst.

Proof. Let m and n be co-prime, that is, gcd(m, n) = 1. As explained in the proof of Lemma 5, the languages L m,k and L n,k can be accepted, respectively, by an m-state k-iufst T 1 and n-state k-iufst T 2 , . Since m and n are co-prime, we have that L(T 1 ) ∩ L(T 2 ) = L m•n,k . This latter language cannot be accepted with less than m • n states on any k-iufst T . Otherwise, by applying to T the construction in Lemma 4, we would obtain a dfa for L m•n,k with less than (m•n) k states, which is a contradiction.

Complementing languages does not increase the size of k-iufst: Theorem 13. Let k, n ≥ 1 be integers and T be an n-state k-iufst. Then n states are sufficient and necessary in the worst case for a k-iufst to accept L(T ).

Proof. For the size upper bound, it is enough to switch accepting and rejecting states on T , thus obtaining an n-state k-iufst for L(T ). For the size lower bound, consider the language L n,k in the proof of Lemma 5. As pointed out, such a language has a minimal dfa with n k states. Suppose, by contradiction, that L n,k can be accepted by a k-iufst M with m < n states. By using on M the switching technique above, an m-state k-iufst M is obtained for L n,k = L n,k . Now, by Lemma 4, M can be turned into an equivalent dfa with m k < n k states, a contradiction.

Finally, we focus on union of languages. We obtain a cost similar to implementing intersection. Theorem 14. Let m, n, k ≥ 1 be integers, T 1 be an m-state k-iufst and T 2 be an n-state k-iufst. Then m • n states are sufficient and necessary in the worst case for a k-iufst to accept L(T 1 ) ∪ L(T 2 ).

Proof. The size upper bound follows from the upper bounds for intersection and complementation by De Morgan's laws.

For the size lower bound, assume by contradiction that less than m • n states are sufficient to implement union on k-iufst. Consider the languages L m,k and L n,k with co-prime m and n, used in Theorem 12 to show the optimality of the cost m • n of intersection on k-iufst. Clearly, we have L m,k ∩ L n,k = L m,k ∪ L n,k . By Theorem 13, for L m,k and L n,k , respectively, m and n states are sufficient on a k-iufst. Yet, by our absurdum assumption, less than m • n states are sufficient to accept their union. In turn, again by Theorem 13, complementing the union language can be done with less than m • n states on a k-iufst. This contradicts Theorem 12.

Let us conclude this section by discussing the cost of performing reversal on k-iufst: Theorem 15. Let k, n ≥ 1 be integers and T be an n-state k-iufst. Then 2 n k states are sufficient and at least 2 n k k2 k states are necessary in the worst case for a k-iufst to accept L(T ) R .

Proof. For the state upper bound, we transform T into an equivalent n k -state dfa A according to Lemma 4. Next, by standard construction [START_REF] Salomaa | On the state complexity of reversals of regular languages[END_REF], A can be turned into a 2 n k -state dfa A for L(A) R = L(T ) R . Finally, by Lemma 6, the dfa A can be simulated by a 2 n k -state k-iufst.

For the state lower bound, let the language C n,k = c>0 {a, b} c•n k -1 b{a, b} * . The minimal dfa for C n,k R has at least 2 n k states, which means, by Lemma 4, that any k-iufst for C n,k R must have at least 2 n k /k states. By suitably adapting the k-iufst for the language L n,k provided in the proof of Lemma 5, we can obtain a 2n-state k-iufst for C n,k . Whence, the claimed result follows.

Decidability Questions for k-IUFSTs

In this subsection, we obtain that all commonly studied decidability questions for k-iufsts are NL-complete So, for k-iufsts the questions of testing emptiness, universality, finiteness, infiniteness, inclusion, or equivalence have the same computational complexity as for dfas [START_REF] Jones | Space-bounded reducibility among combinatorial problems[END_REF][START_REF] Jones | Complete problems for deterministic polynomial time[END_REF].

Theorem 16. Let k ≥ 1 be an integer. Then for k-iufsts the problems of testing emptiness, universality, finiteness, infiniteness, inclusion, and equivalence are NL-complete.

Hierarchy of Non-Constant Sweep Complexities

We turn to consider s(n)-iufsts where s(n) is a non-constant function. Since for any constant k ≥ 1 any k-iufst accepts a regular language, the first natural question is the following: "How many sweeps are necessary to cross the edge to non-regularity?" The answer is that there is no sublogarithmic sweep complexity that gives an iufst the power to accept a non-regular language.

Proposition 17. Let s(n) ∈ o(lg n). The language accepted by any s(n)-iufst is regular.

Proof. From a given s(n)-iufst T , it is not hard to construct an equivalent onetape Turing machine M with time complexity 2n • s(n). It is shown in [START_REF] Hartmanis | Computational complexity of one-tape Turing machine computations[END_REF] that any one-tape Turing machine with a time complexity of order o(n lg n) accepts a regular language. Since s(n) ∈ o(lg n), the time complexity of M is of order o(n lg n) and, thus, L(M ) = L(T ) is regular.

In fact, the gap between constant and 'useful' non-constant sweep complexities ends at a logarithmic level. The witness language given by the following lemma is even unary and non-context-free.

Lemma 18. The non-context-free unary language L uexpo = { a 2 k | k ≥ 0 } is accepted by a six-state s(n)-iufst with s(n) ∈ O(lg n).

Next, we turn to extend the sweep complexity hierarchy beyond the logarithm. To this end, we consider sweep complexities of order O( √ n). The goal is to show that there is a language accepted by some s(n)-iufst with s(n) ∈ O( √ n) that cannot be accepted by any s(n)-iufst with s(n) ∈ o( √ n).

Lemma 19.

(1) The copy language with center markers L cpc = { w$ m w | w ∈ {a, b} * , m ≥ 1 } is accepted by an s(n)-iufst with s(n) ∈ O(n).

(2) The copy language with single marker { w$w | w ∈ {a, b} * } is accepted by an s(n)-iufst with s(n) ∈ O(n).

(3) Let Σ 1 be an alphabet not containing the symbol $ and Σ 2 be an arbitrary alphabet. Then language L eq = { u$v | u ∈ Σ * 1 , v ∈ Σ * 2 , and |u| = |v| } is accepted by some s(n)-iufst with s(n) ∈ O(n).

The second ingredient to show that there is a language accepted by some s(n)-iufst with s(n) ∈ O( √ n) that cannot be accepted by any s(n)-iufst with s ∈ o( √ n) is the acceptance of a language whose word length are quadratic.

Lemma 20. The language L sqr = { #a m-1 #a m-2 • • • #a 1 # | m ≥ 0 } is accepted by an s(n)-iufst with s(n) ∈ O( √ n).

Now we are prepared to provide the witness language

L cpsq = { w$w#a m-1 #a m-2 • • • #a 1 # | m ≥ 0, w ∈ {a, b} m-1 }.
Theorem 21. The language L cpsq is accepted by an s(n)-iufst with s(n) ∈ O( √ n).

To show that the witness language L cpsq is not accepted by any s(n)-iufst with s(n) ∈ o( √ n), we use Kolmogorov complexity and incompressibility arguments.

Theorem 22. The language L cpsq cannot be accepted by any s(n)-iufst with s(n) ∈ o( √ n).

Finally, the sweep complexity hierarchy can be extended beyond the square root. By Lemma 19 we know already that the copy language with center markers L cpc = { w$ m w | w ∈ {a, b} * , m ≥ 1 } is accepted by an s(n)-iufst with s(n) ∈ O(n). The following theorem separates this level of the sweep complexity hierarchy from the one induced by s(n) ∈ O( √ n):

Theorem 23. The copy language with center markers L cpc cannot be accepted by any s(n)-iufst with s(n) ∈ o(n).

Acknowledgements. The authors wish to thank the anonymous referees for useful and kind comments.


Giovanni Pighizzini
email: pighizzini@di.unimi.it

Limited Automata: Properties, Complexity and Variants

Limited automata are single-tape Turing machines with severe rewriting restrictions. They have been introduced in 1967 by Thomas Hibbard, who proved that they have the same computational power as pushdown automata. Hence, they provide an alternative characterization of the class of context-free languages in terms of recognizing devices. After that paper, these models have been almost forgotten for many years. Only recently limited automata were reconsidered in a series of papers, where several properties of them and of their variants have been investigated. In this work we present an overview of the most important results obtained in these researches. We also discuss some related models and possible lines for future investigations.

A Short Introduction with a Classical Example

This paper is devoted to limited automata. These devices have been introduced, with the aim of generalizing the notion of determinism in context-free languages, by Thomas N. Hibbard in 1967, who originally called them scan limited automata. We present an overview of the most important results on limited automata: we discuss their computational power, their descriptional complexity, the relationships between deterministic and nondeterministic versions. Finally, we shortly discuss some variants of these devices and some related models. In the paper we will also address some problems related to these devices which, in our opinion, deserve investigation.

In order illustrate the model, we start by presenting a classical example which will turn out to be useful in the paper.

Suppose we need to verify that a sequence of brackets is correctly balanced. A quite natural way to proceed is to start from the first opening bracket and search for the corresponding closing bracket. To locate it, a counter which is incremented for each opening bracket and decremented for each closing bracket can be helpful. When during this process the counter reaches the initial value, the closing bracket is reached. These operations can be iterated for each opening bracket in order to verify the matching of all the pairs of brackets and the correct nesting in the sequence.

We could use a different and perhaps more simple strategy. Instead of locating the first opening bracket, we start by locating the first closing one: the corresponding opening bracket is necessarily the last bracket before it, that must be of the same type. If these two brackets are removed or rewritten by a different symbol, the same procedure can be repeated on the sequence so modified: locate the first closing bracket, check if the last bracket before it is of the same type, and overwrite these two brackets. When no more closing brackets are left in the sequence, even none opening bracket can be left. In this case the original sequence was balanced. Otherwise, in the following cases the sequence is not balanced:

-At the end, the sequence left on the tape contains some opening bracket.

-After locating a closing bracket, no opening bracket before it is found.

-After locating a closing bracket, the last opening bracket found before it is of a different type.

Suppose now that the sequence of brackets is written on a Turing machine tape, one bracket per cell, and suppose that the computation of the machine starts, as usual, with the head scanning the cell containing the first input symbol. In this way, each input cell is reached for the first time while moving the head from left to right. We can observe that, applying the above described strategy, the following facts hold:

-A cell containing a closing bracket is overwritten only when the head visits it for the first time. After that operation the head is moved back to the left to search an opening bracket. -A cell containing an opening bracket is overwritten only when the head visits it for the second time. In this case the cell is entered by the head from the right.

-After one of these two active visits, a cell can be visited further many times, but it cannot be overwritten, so it is "frozen".

As we will discuss in the paper, each context-free language can be recognized by a strategy similar to the one we just described. In particular, each context-free language can be recognized by a single-tape machine which is able to overwrite the contents of each tape cell only in the first two visits. This is the basic idea under the computational model of limited automata that we discuss in this work. The device we have outlined for this specific case is called 2-limited automaton, since each cell can be overwritten only in the first two visits and, after that, it is never modified.

Limited Automata

Given an integer d ≥ 0, a d-limited automaton is a Turing machine with a single tape, which initially contains the input, one symbol for each tape cell. At the left and at the right of the input there are cells containing the two special symbols and called, respectively, the left and the right end-markers. The machine head cannot leave the tape segment delimited by the two end-markers, i.e., it cannot move to the left of the cell containing and to the right of cell containing .

In d-limited automata, each tape cell can be overwritten only in the first d visits. After that the cell is "frozen", so it cannot be further modified. The cells containing the two end-markers cannot be never overwritten.

Acceptance is defined in a standard way, as for Turing machines. More technical details can be found in [START_REF] Pighizzini | Limited automata and regular languages[END_REF][START_REF] Pighizzini | Limited automata and context-free languages[END_REF]. 1We will now discuss the computational power of these models, in the nondeterministic and deterministic cases. Then, we will present descriptional complexity aspects and several open problems. We will conclude the section by shortly discussing time complexity.

Computational Power, Determinism and Nondeterminism

In Section 1 we described how a 2-limited automaton can accept the language of balanced sequences of brackets. We remind the reader that such a language is called Dyck language. More precisely, given an alphabet Ω k containing k types of brackets (hence 2k symbols) we denote by D k the Dyck language over it.

Dyck languages are important in the investigation of context-free languages, because they capture the recursive structure of any context-free language. This fact is formalized in the following famous result: Theorem 1 (Chomsky-Schützenberger Theorem [START_REF] Chomsky | The algebraic theory of context-free languages[END_REF]). Each context-free language L over an alphabet Σ can be represented as a homomorphic image

L = h(D k ∩ R), for some integer k > 0, where R ⊆ Ω *
k is a regular language and h : Ω k → Σ * is a homomorphism.

Theorem 1 suggests a way to build, for any context-free language L, a recognizer which is the combination of the following devices, as depicted in Figure 1:

-A one-way nondeterministic machine T that on each input w ∈ Σ * produces a string z ∈ h -1 (w). -A machine A D recognizing the Dyck language D k .

-A one-way finite automaton A R accepting the regular language R.

As machine A D we can use the 2-limited automaton for the recognition of D k outlined in Section 1. Using the fact that the homomorphism h can be supposed to be non-erasing [START_REF] Okhotin | Non-erasing variants of the Chomsky-Schützenberger theorem[END_REF], it is possible to combine these machines in such a way that also the resulting machine accepting the given context-free language L is a 2-limited automaton. (Details can be found in [START_REF] Pighizzini | Limited automata and regular languages[END_REF][START_REF] Pighizzini | Guest column: One-tape Turing machine variants and language recognition[END_REF].) This allows to conclude that each context-free language is accepted by a 2-limited automaton.

The converse also holds. Furthermore, by allowing a larger, but still constant number of initial visits in which rewritings are possibles, the computational power does not increase. By summarizing:

T AR AD E w z ∈ h -1 (w) d d z ∈ R? d d z ∈ D k ? E w ∈ L? ∧ Fig. 1. A machine accepting L = h(D k ∩ R).
Theorem 2 ([9]). For each d ≥ 2, the class of languages accepted by d-limited automata coincides with the class of context-free languages.

The just outlined conversion from context-free languages to 2-limited automata is intrinsically nondeterministic. Actually, the conversion presented by Hibbard is different and preserves the determinism. Hence, each deterministic context-free language is accepted by a deterministic 2-limited automaton. However, determinism is not preserved by the converse transformation in the form presented in [START_REF] Hibbard | A generalization of context-free determinism[END_REF]. Indeed, the problem of the equivalence between the class of deterministic context-free language and the class of languages accepted by deterministic 2-limited automata was left open in that paper. This problem was recently solved in [START_REF] Pighizzini | Limited automata and context-free languages[END_REF], by giving a transformation from 2-limited automata to pushdown automata which preserves the determinism. The transformation is based on an extension of transition tables, originally introduced by Shepherdson [START_REF] Shepherdson | The reduction of two-way automata to one-way automata[END_REF] to obtain a simulation of two-way finite automata by equivalent one-way ones.

Theorem 3 ([29]

). The class of languages accepted by deterministic 2-limited automata coincides with the class of deterministic context-free languages.

It is an easy observation that Theorem 3 cannot be extended to d > 2. For instance, the following language, which is not deterministic, can be accepted by a deterministic 3-limited automaton A:

L = {a n b n c | n ≥ 0} ∪ {a n b 2n d | n ≥ 0} .
To recognize L, A can scan the tape from left to right, to locate the right endmarker and, moving back, it can read the last input symbol. If the symbol is a c, then A has to verify whether or not the number of the a's in the input coincides with the number of the b's. To this aim, A continues to move to the left, to find a cell containing an a, which is rewritten by the symbol X. Then it moves to the right to search a cell containing a b, which is also rewritten by the symbol X. This process is repeated up to reach the left end-marker while searching an a. When the last symbol of the input is a d, the only difference in the procedure is that for each a the automaton A has to overwrite two occurrences of the letter b.

We point out that the main motivation of the original work of Hibbard was to extend the notion of determinism for context-free languages (indeed, the title of [START_REF] Hibbard | A generalization of context-free determinism[END_REF] is "A Generalization of Context-Free Determinism"). With respect to the number d of initial visits in which rewriting are allowed, by extending the last example he proved the existence of an infinite hierarchy of deterministic languages: Theorem 4 ( [START_REF] Hibbard | A generalization of context-free determinism[END_REF]). For each d > 2 there exists a language which is recognized by a deterministic d-limited automaton, but which cannot be accepted by any deterministic (d -1)-limited automaton.

In [START_REF] Hibbard | A generalization of context-free determinism[END_REF] it is claimed (without proof) that the set of palindromes cannot be accepted by deterministic d-limited automata, for any integer d. As a consequence, the above hierarchy of deterministic languages does not cover all the class of contextfree languages. It would be interesting to have a formal proof of this fact.

Results comparing the degrees of nondeterminism that can be defined according to the above hierarchy and measures of nondeterminism for pushdown automata are presented in [START_REF] Nasyrov | Deterministic realization of nondeterministic computations with a low measure of nondeterminism[END_REF].

By allowing to overwrite tape cells only in the first visit, the computational power of limited automata reduces to the class of regular languages.

Theorem 5 ([34, Thm. 12.1]). The class of languages accepted by 1-limited automata coincides with the class of regular languages.

Concerning the computational power of limited automata, we finally mention the case where the number of initial visits to each cell in which rewritings are possible is not constant, but it is bounded by a function f (n) of the input length n. This case was studied by Wechsung and Brandstädt which gave a characterization in terms of languages accepted by space bounded one-way auxiliary pushdown automata, namely pushdown automata with a one-way input tape, extended with a two-way work tape. The space is measured by taking into account only the work tape.

Theorem 6 ([36]

). For any recursive function f (n), the class of languages accepted by f (n)-limited automata coincides with the class of languages accepted by auxiliary pushdown automata in space O(f (n)).

Descriptional Complexity

To study the descriptional complexity of a formal system, we have to consider the size of its description, namely the number of symbols which are used to write down its description. In the case of limited automata over a given input alphabet Σ, the size is a polynomial in the cardinalities of the state set and of the working alphabet. For pushdown automata we also have to take into account how many symbols can be written on the pushdown store in one single move. However, if each move is allowed to increase the height of the pushdown by adding at most one symbol, then the size is polynomial in the number of states and in the cardinality of the pushdown alphabet. In a similar way, to define the size of context-free grammars, we have to take into account the maximal length of the right-hand sides of productions. For grammars in Chomsky normal form or, more in general, grammars in which the production right-hand sides have length at most 2, the size is polynomial in the number of variables. Finally, for finite automata, the size is polynomial with respect to the number of states.

We introduce a family of languages which will be useful to discuss descriptional complexity results.

For each integer n > 0, let K n be the set of all strings over the alphabet {a, b} consisting of the concatenation of blocks of length n, where the last block is equal to one of the previous blocks. Formally:

K n = {x 1 • • • x k x | k > 0, x 1 , . . . , x k , x ∈ {a, b} n , ∃j, 1 ≤ j ≤ k, x j = x} .
A deterministic 2-limited automaton for K n To accept K n , a deterministic 2-limited automaton M n can first make a scan from left to right of the input to locate the right end-marker (this "consumes" the first visit to each tape cell). Then M n inspects each block x j of length n starting from j = k up to j = 1, and compares it, symbol by symbol, with the last block x. This can be done by moving the head back and forth between the block under consideration and the last block, using a counter modulo n to identify the corresponding positions that need to be compared in the two blocks, while marking the symbols of x j . In this phase or in the first scan, M n also checks if the length of the input is a multiple of n. The implementation of M n can be done by using O(n) states and a working alphabet of O(1) symbols.

A nondeterministic 1-limited automaton for K n In a first complete scan of the tape, the automaton nondeterministically marks two cells. No more rewriting operations are possible after this phase. The first marked cell is guessed to be the leftmost position of the required block x j , while the other one is guessed to be the leftmost position of the last block x. In a second phase, using a counter modulo n, the machine can verify that the input length is a multiple of n, the last marked position corresponds to the leftmost symbol of the last block of length n, and the other marked position is the leftmost symbol of another block of length n. Finally, the automaton makes n scans of the part of the tape which contains the two selected blocks: in the ith scan it checks if the ith symbols in the marked blocks are equal. The implementation produces a nondeterministic 1-limited automaton with O(n) states.

Lower bounds for K n

The following lower bounds for the recognition of K n by pushdown and finite automata can be proved:

-To accept and to generate K n , pushdown automata and context-free grammars require exponential size in n.

The proof can be done by using the interchange lemma for context-free languages [START_REF] Ogden | An "interchange lemma" for contextfree languages[END_REF]. The argument is similar to that used in [START_REF] Pighizzini | Limited automata and context-free languages[END_REF] for a slightly different language.

-Any one-way deterministic automaton accepting K n requires a number of states double exponential in n.

The proof uses distinguishability arguments. Let x 1 , x 2 , . . . , x 2 n be a list of all strings in {a, b} n , in some fixed order, and F be the set of all functions from {1, 2, . . . , 2 n } to {0, 1}. For each f ∈ F , consider the string

w f = x f (1) 1 x f (2) 2 • • • x f (2 n ) 2 n
. Given f, g ∈ F , with f = g, it can be verified that any string x i with f (i) = g(i) distinguishes w f and w g . Since #F = 2 2 n , the lower bound follows.

The size cost of the simulation of 2-limited automata by pushdown automata has been investigated in [START_REF] Pighizzini | Limited automata and context-free languages[END_REF] by proving an exponential upper bound. The result has been recently improved, by showing that the upper bound remains exponential if we simulate a d-limited automaton, with d > 2, by a pushdown automaton [START_REF] Kutrib | Descriptional complexity of limited automata[END_REF]. Considering the lower bound given for the size of pushdown automata accepting K n , we obtain: Theorem 7 ( [START_REF] Pighizzini | Limited automata and context-free languages[END_REF][START_REF] Kutrib | Descriptional complexity of limited automata[END_REF]). For each d > 1, the size cost of the transformation of dlimited automata into equivalent pushdown automata is exponential.

Concerning the transformation of deterministic 2-limited automata into equivalent deterministic pushdown automata, it has been proved a double exponential upper bound, which reduces to a simple exponential if the input is given to the pushdown automaton with an extra special symbol marking the right end. The optimality of the exponential bounds can be proved using K n . We conjecture that the double exponential upper bound cannot be reduced.

For the converse transformations, we have the following result:

Theorem 8 ( [START_REF] Pighizzini | Limited automata and context-free languages[END_REF]). The size cost of the transformation of pushdown automata into 2-limited automata is polynomial. Furthermore, the polynomial transformation preserves determinism.

By Theorem 5, 1-limited automata have the same power of finite state automata. The proof of this result was obtained by Wagner and Wechung by adapting the Shepherdson's technique for the transformation of two-way finite automata into equivalent one-way ones [START_REF] Shepherdson | The reduction of two-way automata to one-way automata[END_REF]: given a 1-limited automaton, a nondeterministic one-way automaton is created which keeps in its state a transition table corresponding to the portion of the tape at the left of the head. The table is used to replace parts of computations that from the current head position finally reach for the first time the position to the right of it, by making a sequence of moves which visit some of the already scanned tape cells.

By analyzing the cost of such a simulation and by considering the family of languages K n , the following costs can be obtained: Theorem 9 ( [START_REF] Pighizzini | Limited automata and regular languages[END_REF]). The size costs of the transformation of 1-limited automata into equivalent one-way nondeterministic and deterministic finite automata are exponential and double exponential, respectively.

We point out that the double exponential cost in Theorem 9 is related to a double role of the nondeterminism in 1-limited automata. When the head of a 1limited automaton reaches for the first time a tape cell, it overwrites the contents according to a nondeterministic choice. 2 Furthermore, the set of nondeterministic choices that are allowed during the next visits to the same cell depends on the symbol that has been chosen to rewrite it in the first visit and that cannot be further changed, namely it depends on the nondeterministic choice which was made during the first visit.

When the given 1-limited automaton is deterministic, the same simulation produces a one-way deterministic finite automaton of exponential size. The optimality can be easily proved by considering the reversal of the language K n .

We briefly discuss the unary case, namely, the case of languages defined over a one-letter alphabet. It is well known that, under this restriction, the classes of context-free and of regular languages coincide [START_REF] Ginsburg | Two families of languages related to ALGOL[END_REF]. Hence, for each d ≥ 0, unary d-limited automata recognize only regular languages. Since the family K n of witness languages used in Theorem 9 is defined over a binary alphabet, it is quite natural to ask if there is any difference in the unary case.

A first result comparing the sizes of unary 1-limited automata and those of equivalent two-way nondeterministic finite automata was presented in [START_REF] Pighizzini | Limited automata and regular languages[END_REF]. Kutrib and Wendlandt proved state lower bounds for the simulation of unary dlimited automata by different variants of finite automata [START_REF] Kutrib | On simulation cost of unary limited automata[END_REF][START_REF] Kutrib | Descriptional complexity of limited automata[END_REF]. More recently, the following result has been proved: Theorem 10 ( [START_REF] Pighizzini | Limited automata and unary languages[END_REF]). For each integer n > 0, the singleton language {a 2 n } is accepted by a deterministic 1-limited automaton of size O(n), while each one-way nondeterministic finite automaton accepting it needs 2 n + 1 states.

The upper bound in Theorem 10 was obtained by making use of the construction and of the properties of the binary carry sequence, an infinite sequence of integers related base 2 representation [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF].

With a small modification, it can be shown that for each n > 0 even the language {a 2 n } * can be accepted by a deterministic 1-limited automaton of size O(n), while each two-way nondeterministic finite automaton accepting it requires 2 n states [START_REF] Pighizzini | Limited automata and unary languages[END_REF].

The results comparing the sizes of finite automata and 1-limited automata are summarized in Figure 2. The upper bounds in the diagram follow from the simulations of 1-limited automata by finite automata (see Theorem 9 and the discussion after it). All the lower bounds, with the exception of those from 1limited automata to one-way deterministic finite automata (arrow (a) in Figure 2) and to deterministic 1-limited automata (b), are witnessed by the unary language {a 2 n } * . For the double exponential lower bound from 1-limited automata to one-way deterministic automata (a), the binary witness K n can be used. It is an open problem if the same gap can be achieved in the unary case. 2 We could have moves that do not change the contents of a cell even in the first visit, as we seen in the above example of 1-limited automaton accepting Kn. For a such a move, we can imagine that the cell is rewritten by the same symbol which is already in it. From our experience on unary languages we conjecture a negative answer. The exponential lower bound from 1-limited automata to deterministic 1-limited automata (b) is a consequence of the double exponential lower bound to one-way deterministic automata (a) and of the cost of the simulation of deterministic 1-limited automata by one-way deterministic automata (d).

At the moment we do not know direct simulations of 1-limited automata by deterministic 1-limited automata (b) and by two-way deterministic automata (c). For instance, it should be interesting to know if simulating 1-limited automata by two-way (instead of one-way) deterministic automata the cost reduces from a double exponential to a simple exponential.

By summarizing, we can propose the following problems:

Problem 1. Study the size cost of the simulation of unary 1-limited automata by one-way deterministic finite automata (unary version of (a)).

Problem 2. Study the size cost of the simulation of 1-limited automata by deterministic 1-limited automata, in the general and in the unary case (b).

Problem 3. Study the size cost of the simulation of 1-limited automata by twoway deterministic finite automata, in the general and in the unary case (c).

We point out that the last two problems are variants of the question of the cost of the elimination of nondeterminism from two-way automata, proposed by Sakoda and Sipser in 1978 [START_REF] Sakoda | Nondeterminism and the size of two way finite automata[END_REF], which is still open (for a recent survey, see [START_REF] Pighizzini | Two-way finite automata: Old and recent results[END_REF]). In particular, concerning Problem 2, we observe that for the elimination of the nondeterminism from 1-limited automata an exponential lower bound is known, while for the corresponding problem in two-way finite automata the best known lower bound is polynomial [START_REF] Chrobak | Finite automata and unary languages[END_REF].

It could be also interesting to study a "relaxed" version of the problem of Sakoda and Sipser, in which the simulating machine could overwrite the contents of tape cells during the first visit: Problem 4. Study the size costs of the simulations of one-way and two-way nondeterministic finite automata by deterministic 1-limited automata.

A relaxed version of the Sakoda and Sipser problem has been recently considered in [START_REF] Guillon | Two-way automata and onetape machines -Read only versus linear time[END_REF], by proving a polynomial blowup from two-way nondeterministic automata to single-tape deterministic machines working in linear time. Since each 1-limited automaton can be converted into an equivalent one working in linear time also preserving determinism (see Theorem 11 below), proving that the simulation proposed in Problem 4 costs polynomial would improve that result.

Problem 4 can be further relaxed by considering simulations by deterministic d-limited automata, for d > 1.

Time Complexity

While one-way and two-way finite automata can always accept in linear time, with respect to the input length, there are 1-limited automata that use quadratic time [START_REF] Guillon | Linear-time limited automata[END_REF].

The Shepherdson's technique, used by Wagner and Wechsung to prove Theorem 5, has been recently refined to prove that, with only a polynomial increase in the size, 1-limited automata can be forced to work in linear time. Roughly, the main idea is that the running time of 1-limited automata can be reduced by avoiding computation paths which move back to the left and visit too many tape cells before reaching again the current position. This is done with a tricky simulation which stores transition tables on a tape track.

Theorem 11 ([6]). With a polynomial size increase, each 1-limited automaton can be transformed into an equivalent 1-limited automaton which works in linear time. Furthermore, determinism can be preserved in such a conversion.

We point out that the machine obtained in Theorem 11 is also a Hennie machines, namely, a single-tape Turing machine working in linear time. It is known that these devices can recognize only regular languages. 3In our knowledge, at the moment there are no other results concerning the time complexity of limited automata.

Strongly Limited Automata

In Section 2, using the Chomsky-Schützenberger representation theorem (Theorem 1), we discussed how to construct for any context-free language a 2-limited automaton accepting it. We remind the reader that such a 2-limited automaton is obtained by combining three machines T , A R and A D , as summarized in Figure 1. While T and A R are finite state machines, A D is the only "context-free component" in the construction. In fact, its purpose is that of recognizing a Dyck language D k . A D can be implemented as the 2-limited automaton described in Section 1. However, we can notice that in order to recognize D k , A D does not use all the capabilities of 2-limited automata. For instance, it moves from left to right only to search closing brackets: in this phase, A D does not need neither to change the state nor to make any rewriting, except when it finally reaches the cell containing a closing bracket, where it starts to move to the left to search a symbol not yet overwritten, which is expected to be the corresponding opening bracket. While moving to the left, A D ignores the contents of cells that have been already overwritten.

Since, as we wrote, A D is the only "context-free component" in the construction and it can be implemented without using all the capabilities of 2-limited automata, we can ask if it is possible to restrict the moves of 2-limited automata, without reducing the computational power.

In [START_REF] Pighizzini | Strongly limited automata[END_REF] we gave a positive answer to this question, by introducing strongly limited automata, a restriction of 2-limited automata which closely imitates the moves that are used by limited automata to accept Dyck languages. In particular, strongly limited automata satisfy the following restrictions:

-While moving to the right, a strongly limited automaton always uses the initial state q 0 until a cell (which has not been yet overwritten) is modified.

Then, it enters a different state and starts to move to the left. -While moving to the left, the automaton ignores the cells that have been already overwritten and, without changing its internal state, overwrites the other ones it meets, up to some position where it enters q 0 and starts again to move to the right. -In the final phase of the computation, which starts when the right endmarker is reached, the automaton inspects all tape cells, to check whether or not the string which is finally on the tape belongs to a given 2-strictly locally testable language. Roughly, this means that all the factors of two letters of this string (including the end-markers) belong to a given set.

We shortly discuss some examples (for more examples see [START_REF] Pighizzini | Guest column: One-tape Turing machine variants and language recognition[END_REF][START_REF] Pighizzini | Strongly limited automata[END_REF]).

Example 1. The language L = {a n b n | n ≥ 0} can be accepted by a strongly limited automaton which in the initial state q 0 moves the head to the right to search the first cell containing a b. When it finds such a cell, it rewrites the contents by the symbol X and moves the head to the left, until it finds the first not overwritten symbol, which is expected to be an a. If so, the symbol is overwritten, the automaton re-enters the state q 0 to search another b. When no more b's are left on the tape, the head reaches the right end-marker. At this point the automaton verifies if the string on the tape is of the form X * .

Example 2. A more interesting example is the recognition of the deterministic context-free language {a n b 2n | n ≥ 0}, which can be done by a strongly lim-ited automaton that guesses the position of each second b, using the following strategy:

-Moving the head from left to right, when the automaton reads an a it continues to move to the right, while when it reads a b it makes a nondeterministic choice between further moving to the right (so leaving the b in the cell) or rewriting the cell by X and turning the head to the left. -Moving the head from right to left, when the automaton reads a b it rewrites it by Y and continues to move to the left (notice that such a b was left unchanged in the previous visit, when moving from left to right), while when it reads an a, it replaces the contents by Z, turning the head to the right. -In the final scan, which starts when the right end-marker is reached, the machine accepts if and only if the string on the tape belongs to Z * (YX) * .

We can modify the above algorithm in order to recognize the language {a n b n | n ≥ 0}∪{a n b 2n | n ≥ 0}. While moving from left to right, when the head reaches a cell containing b three actions are possible: either the automaton continues to move to the right, without any rewriting, or it rewrites the cell by X, turning to the left, or it rewrites the cell by W, also turning the head to the left. While moving from right to left, the automaton behaves as the one above described for {a n b 2n | n ≥ 0}. The input is accepted if and only if the string which is finally on the tape belongs to Z * W * + Z * (YX) * .

In spite of the restrictions on moves, strongly limited automata have the same computational power as limited automata, namely they characterize contextfree languages. Furthermore they are polynomially related in size to pushdown automata: Theorem 12 ( [START_REF] Pighizzini | Strongly limited automata[END_REF]).

(i) Each context-free language L is accepted by a strongly limited automaton whose description has a size which is polynomial with respect to the size of a given context-free grammar generating L or of a given pushdown automaton accepting L. (ii) Each strongly limited automaton M can be simulated by a pushdown automaton of size polynomial with respect the size of M.

The proof of (i) was obtained using a variant of the representation theorem of Chomsky-Schützenberger, proved by Okhotin [START_REF] Okhotin | Non-erasing variants of the Chomsky-Schützenberger theorem[END_REF], where Dyck languages extended with neutral symbols and letter-to-letter homomorphisms are used.

(ii) was proven by providing a direct simulation.

In Example 2 we described a strongly limited automaton accepting the deterministic context-free language {a n b 2n | n ≥ 0}. The automaton makes use of nondeterministic choices. It is not difficult to prove that this cannot be avoided (see [START_REF] Pighizzini | Strongly limited automata[END_REF]). Hence: Theorem 13 ( [START_REF] Pighizzini | Strongly limited automata[END_REF]). The class of languages accepted by deterministic strongly limited automata is properly included in the class of deterministic context-free languages.

Strongly limited automata are allowed to change state only when they reverse the head direction. If we remove this restriction, the language {a n b 2n | n ≥ 0} (and other deterministic context-free languages which are not accepted by deterministic strongly limited automata) can be easily recognized in a deterministic way. In order to have a model polynomially related in size to pushdown automata and whose deterministic version is equivalent to deterministic pushdown automata, in [START_REF] Pighizzini | Strongly limited automata[END_REF] almost strongly limited automata have been proposed. They are obtained from strongly limited automata by relaxing some of the restrictions on state changes. In almost strongly limited automata there is a set of states Q R , including the initial state q 0 , which can be used while moving to the right, and a set of states Q L which can be used while moving to the left. State changes are possible while moving to the left or to the right (which is not possible in strongly limited automata), except on the cells that have been already overwritten. Furthermore, almost strongly limited automata have to satisfy all the other restrictions given for strongly limited automata.

By adapting the arguments used to prove Theorem 12, it can be shown that almost strongly limited automata characterize context-free languages and are polynomially related in size to pushdown automata. Since almost strongly limited automata are restrictions of 2-limited automata, from Theorem 3 it follows that each deterministic almost strongly limited automaton recognizes a deterministic context-free language. At the moment, we do not know if the converse holds.

Problem 5. Does the class of languages accepted by deterministic almost strongly limited automata coincide with the class of deterministic context-free languages?

Some Related Models

In this section we shortly discuss some restricted variants of Turing machines, presented in the literature, which recognize context-free languages.

Wechsung's Model

We have seen that limited automata are single-tape Turing machines defined by limiting the active visits to each tape cell from the beginning of the computation: in a d-limited automaton only the first d visits to each cell can modify the contents.

We can consider a similar restriction, where for a fixed integer d, only the last d visits to each cell can be active.

Such a model was implicitly introduced by Wechsung, by considering a complexity measure for one-tape Turing machines called return complexity [START_REF] Wechsung | Characterization of some classes of context-free languages in terms of complexity classes[END_REF][START_REF] Wechsung | A relation between space, return and dual return complexities[END_REF]. Indeed, this measure counts the maximum number of visits to a tape cell, starting from the first visit which modifies the cell contents. Machines with return complexity 1 characterize regular languages (each cell, after the first rewriting, will be never visited again, hence rewritings are useless). Furthermore, it has been shown that for each d ≥ 2, return complexity d characterizes context-free languages. 4 Even with respect to return complexity, there exists a hierarchy of deterministic languages (cf. Theorem 4 in the case of limited automata). However, this hierarchy is not comparable with the class of deterministic context-free languages. For instance, it can be easily seen that the set of palindromes, which is not a deterministic context-free language, can be recognized by a deterministic machine with return complexity 2. However, there are deterministic context-free languages that cannot be recognized by any deterministic machine with return complexity d, for any integer d [START_REF] Peckel | On a deterministic subclass of context-free languages[END_REF][START_REF] Peckel | A deterministic subclass of context-free languages[END_REF].

It seems interesting to investigate the possibility of finding a class of machines containing both limited automata and Wechsung's machines and still characterizing context-free languages. One natural attempt can be that of considering machines such that for each tape cell the number of visits counted starting from the first active visit up to the last one is bounded by a given constant.

Forgetting, Deleting and Restarting Automata

With motivations deriving mainly from linguistics, in a series of papers Jancar, Mráz, and Plátek introduced and studied forgetting automata [START_REF] Jančar | Characterization of context-free languages by erasing automata[END_REF][START_REF] Jančar | A taxonomy of forgetting automata[END_REF][START_REF] Jančar | Forgetting automata and context-free languages[END_REF]. These devices are single-tape machines that can erase tape cells by rewriting their contents with a unique special symbol, that cannot be further overwritten. However, overwritten cells are kept on the tape and are still considered during the computation. For instance, the state can be changed while visiting an erased cell. Different variants, depending on the allowed operations, have been investigated.

In a variant of forgetting automata that characterizes context-free languages, when a cell which contains an input symbol is visited while moving to the left, it is rewritten by the unique special symbol, while it can remain unchanged while moving to the right. This way of operating has some similarities with that of strongly limited automata, which, however, can use nonunary rewriting alphabets. 5 Furthermore, in strongly limited automata overwritten cells are completely ignored (namely, the head direction and the state cannot be changed while visiting them) except in the final scan of the tape from the right to the left end-marker.

If erased cells are completely ignored in forgetting automata, the resulting computational model, called deleting automata, is less powerful. In fact it is not able to recognize all context-free languages [START_REF] Jančar | Forgetting automata and context-free languages[END_REF].

A modification of forgetting automata, called restarting automata, was introduced in [START_REF] Jančar | Restarting automata[END_REF] and widely considered in the literature. Variants of restarting automata characterizing context-free languages have been obtained. For more details see [START_REF] Otto | Restarting automata and their relations to the Chomsky hierarchy[END_REF].

No Space Overhead Machines

With the aim of investigating computations with very restricted resources, Hemaspaandra, Mukherji, and Tantau studied single-tape Turing machine with absolutely no space overhead [START_REF] Hemaspaandra | Context-free languages can be accepted with absolutely no space overhead[END_REF]. The model is very close to "realistic computations", where the space is measured without any hidden constants. To this aim, these machines use the binary alphabet Σ = {0, 1} (plus two end-marker symbols) and only the portion of the tape which at the beginning of the computation contains the input. Furthermore, no other symbols are available, namely only symbols from Σ can be used to rewrite the tape. Despite these strong restrictions, these machines are able to recognize in polynomial time all context-free languages over Σ.

Further Remarks

In this work we presented limited automata, discussed some of their main properties, in particular concerning computational power, descriptional complexity, determinism versus nondeterminism. We shortly discussed some related models. This overview is only partial. Much more space would be necessary to make an exhaustive and more detailed work.

We conclude by adding a couple of further remarks. First we point out that reversibility in limited automata has been investigated in [START_REF] Kutrib | Reversible limited automata[END_REF]. Probabilistic extensions of limited automata have been recently introduced and studied in [START_REF] Yamakami | Behavioral strengths and weaknesses of various models of limited automata[END_REF].

We do not know any result relating limited automata, or their variants, with input-driven pushdown automata, also known as nested word automata [START_REF] Mehlhorn | Pebbling moutain ranges and its application of DCFL-recognition[END_REF][START_REF] Alur | Adding nesting structure to words[END_REF]. It is known that these devices recognize a proper subclass of deterministic contextfree languages, which properly contains the class of regular languages. It should be interesting to know if this class can be characterized by some restricted versions of limited automata.

Fig. 2 .

 2 Fig.2. State costs of conversions of 1-limited automata (1-la) and deterministic 1limited automata (d1-la) into equivalent one-way and two-way deterministic and nondeterministic finite automata (1dfa, 1nfa, 2dfa, 2nfa).

Actually, the original definition of d-limited automata was given by Hibbard by considering some kinds of rewriting systems[START_REF] Hibbard | A generalization of context-free determinism[END_REF]. It is not difficult to reformulate it, as we did, in terms of Turing machines.

The proof of this result has been given by Hennie, for the deterministic case[START_REF] Hennie | One-tape, off-line Turing machine computations[END_REF]. Several improvements have been presented in the literature. See[START_REF] Pighizzini | Nondeterministic one-tape off-line Turing machines[END_REF] for a survey.

The maximum number of visits to a cell up to the last rewriting, namely the measure corresponding to limited automata, is sometimes called dual return complexity[START_REF] Wagner | Computational Complexity[END_REF].

A nonunary rewriting alphabet is necessary for strongly limited automata to recognize all context-free languages. For instance, to recognize the set of palindromes, a working alphabet of at least 3 symbols is required[START_REF] Pighizzini | Strongly limited automata[END_REF].

Acknowledgment

I am very grateful to Luca Prigioniero for his valuable and helpful comments.