Alexander Okhotin
email: alexander.okhotin@spbu.ru

Kai Salomaa
email: ksalomaa@cs.queensu.ca

Further Closure Properties of Input-Driven Pushdown Automata

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Input-driven pushdown automata (IDPDA), also known under the name of visibly pushdown automata, are an important special class of pushdown automata, introduced by Mehlhorn [START_REF] Mehlhorn | Pebbling mountain ranges and its application to DCFLrecognition[END_REF] and later studied, in particular, by Alur and Madhusudan [START_REF] Alur | Visibly pushdown languages[END_REF][START_REF] Alur | Adding nesting structure to words[END_REF]. In these automata, the input symbol determines whether the automaton should push a stack symbol, pop a stack symbol or leave the stack untouched. These symbols are called left brackets, right brackets and neutral symbols, and the symbol pushed at each left bracket is always popped when reading the corresponding right bracket. Input-driven automata are important as a model of hierarchically structured data, such as XML documents or computation traces for recursive procedure calls.

Input-driven automata exist in deterministic (DIDPDA) and nondeterministic (NIDPDA) variants, which, as shown by von Braunmühl and Verbeek [START_REF] Braunmühl | Input driven languages are recognized in log n space[END_REF], are equivalent in power. Input-driven automata are also notable for their appealing closure properties, which almost rival those of finite automata. For instance, they are closed under all Boolean operations, concatenation, Kleene star, reversal [START_REF] Alur | Visibly pushdown languages[END_REF][START_REF] Okhotin | State complexity of operations on input-driven pushdown automata[END_REF], quotient [START_REF] Okhotin | The quotient operation on input-driven pushdown automata[END_REF]. and edit distance neighbourhood [START_REF] Okhotin | Edit distance neighbourhoods of input-driven pushdown automata[END_REF] (for binary operations it is assumed that the automata defining its two arguments use the same Supported by Russian Science Foundation, project 18-11-00100.

partition of the alphabet into classes), Besides the closure results, the descriptional complexity of these operations has also been estimated in the literature. For instance, the concatenation of an m-state and an n-state DIDPDA in the worst case requires a DIDPDA with m2 Θ(n log n) states [START_REF] Okhotin | State complexity of operations on input-driven pushdown automata[END_REF], whereas both for the union and for the intersection its state complexity is Θ(mn) [START_REF] Piao | Operational state complexity of nested word automata[END_REF]. For NIDPDA, the state complexity of concatenation and of union is m+n+O(1) [START_REF] Alur | Visibly pushdown languages[END_REF], and for the intersection it is Θ(mn) [START_REF] Han | Nondeterministic state complexity of nested word automata[END_REF]. Further state complexity results were established for an intermediate family of unambiguous input-driven automata (UIDPDA) [START_REF] Okhotin | Descriptional complexity of unambiguous input-driven pushdown automata[END_REF]. For more details on input-driven automata and their complexity, the readers are directed to a fairly recent survey [START_REF] Okhotin | Complexity of input-driven pushdown automata[END_REF].

The purpose of this paper is to investigate the closure and the state complexity of input-driven pushdown automata with respect to several further operations on languages, which are fairly standard in the theoretical research in formal language theory-yet their application to IDPDA has not yet been considered.

The first operation, investigated in

Section 3, is insertion, ins(L, K) = { xyz | xz ∈ L, y ∈ K }.
For finite automata, the closure under this operation is folklore, and its precise state complexity has recently been determined by Han et al. [START_REF] Han | State complexity of insertion[END_REF]. For input-driven automata, the closure is currently known only for singleton K [START_REF] Okhotin | Edit distance neighbourhoods of input-driven pushdown automata[END_REF]. This paper demonstrates the closure under the assumption that K consists only of well-nested strings, and determines the worst-case number of states in an NIDPDA recognizing ins(L, K) as mn + 2m, where m is the number of states in the NIDPDA for K, while the NIDPDA for L has n states. For unrestricted K, the non-closure is established.

Another related operation is deletion, del(L, K) = { xz | ∃y ∈ K : xyz ∈ L }.
It is well-known that if L is regular, then the result is regular for an arbitrary K. The state complexity of this operation for finite automata has recently been studied by Han et al. [START_REF] Han | State complexity of deletion and bipolar deletion[END_REF]. For NIDPDA, as shown in Section 4, del(L, K) is representable with 2n states, as long as K consists only of well-nested strings; without this assumption, there is a non-closure result.

The third operation, studied in Section 5, is the square root,

√ L = { w | ww ∈ L }.
Assuming that L consists of only well-nested strings and is recognized by an n-state DIDPDA, its square root can be represented by a DIDPDA with n n states, and this bound is tight; this proof uses the behaviour functions of DIDPDA [START_REF] Okhotin | Input-driven languages are linear conjunctive[END_REF][START_REF] Okhotin | State complexity of operations on input-driven pushdown automata[END_REF] in the same way as in the similar result for deterministic finite automata (DFA) [START_REF] Maslov | Estimates of the number of states of finite automata[END_REF]. For NIDPDA, as well as for nondeterministic finite automata (NFA), it is shown that this operation requires at most n 3 states and at least (n -1)(n -2)(n -3) states in the worst case. If L is not restricted to well-nested strings, a non-closure is established. Section 6 considers the operation of taking the first half of all even-length strings in a language, 1 2 L = {u | ∃v : |u| = |v|, uv ∈ L}. This is a particular case of proportional removals, studied by Maslov [START_REF] Maslov | Estimates of the number of states of finite automata[END_REF] and by Domaratzki [START_REF] Domaratzki | State complexity of proportional removals[END_REF] for DFA, and by Goč et al. [START_REF] Goč | Nondeterministic state complexity of proportional removals[END_REF] for NFA. For NIDPDA, if L consists of well-nested strings, then 1 2 L is recognized by an NIDPDA with 2 O(n 2 ) states. For not necessarily well-nested L, there is again a non-closure.

a < b > c < < a b > c > d γ γ γ' γ' γ'' γ' γ'' γ' γ' γ'
γ'' q 6 q q 1 q 2 q 3 q 4 q 5 q 12 q' q 7 q 9 q 10 q 11 q 8 Fig. 1. The computation of an IDPDA on a well-nested string.

The last Section 7 proposes an open problem on the state complexity of scattered substrings for IDPDA.

Input-driven automata

A deterministic input-driven pushdown automaton (DIDPDA) [START_REF] Alur | Visibly pushdown languages[END_REF][START_REF] Mehlhorn | Pebbling mountain ranges and its application to DCFLrecognition[END_REF] is a special case of a deterministic pushdown automaton, in which the input alphabet Σ is split into three disjoint sets of left brackets Σ +1 , right brackets Σ -1 and neutral symbols Σ 0 . If the input symbol is a left bracket from Σ +1 , then the automaton always pushes one symbol onto the stack. For a right bracket from Σ -1 , the automaton must pop one symbol. Finally, for a neutral symbol in Σ 0 , the automaton may not use the stack. In this paper, symbols from Σ +1 and Σ -1 shall be denoted by left and right angled brackets, respectively (<, >), whereas lower-case Latin letters from the beginning of the alphabet (a, b, c, . . .) shall be used for symbols from Σ 0 .

A nondeterministic input-driven pushdown automaton (NIDPDA) [START_REF] Alur | Visibly pushdown languages[END_REF][START_REF] Braunmühl | Input driven languages are recognized in log n space[END_REF] is a similarly restricted case of a nondeterministic pushdown automaton, in which the type of the action on the stack is determined by the input symbol, whereas the actual next state and the symbol pushed onto the stack may be selected nondeterministically.

Input-driven automata are often restricted to operate on input strings, in which the brackets are well-nested. When an input-driven automaton reads a left bracket < ∈ Σ +1 , it pushes a symbol onto the stack. This symbol is popped at the exact moment when the automaton encounters the matching right bracket > ∈ Σ -1 . Thus, a computation of an input-driven automaton on any well-nested substring leaves the stack contents untouched, as illustrated in Figure 1.

Alur and Madhusudan [START_REF] Alur | Visibly pushdown languages[END_REF] also considered input-driven automata operating on potentially ill-nested input strings. For every unmatched left bracket, the symbol pushed to the stack when reading this bracket is never popped, and remains in the stack to the end of the computation. An unmatched right bracket is read with an empty stack: instead of popping a stack symbol, the automaton merely detects that the stack is empty and makes a special transition, which leaves the stack empty.

Definition 1 (von Braunmühl and Verbeek [START_REF] Braunmühl | Input driven languages are recognized in log n space[END_REF]; Alur and Madhusudan [START_REF] Alur | Visibly pushdown languages[END_REF]). A nondeterministic input-driven pushdown automaton (NIDPDA) over an alphabet Σ = (Σ +1 , Σ -1 , Σ 0 ) consists of a finite set Q of states, with set of initial states Q 0 ⊆ Q and accepting states F ⊆ Q; a finite stack alphabet Γ , and a special symbol ⊥ / ∈ Γ for the empty stack; for a neutral symbol c ∈ Σ 0 , a transition function δ c : Q → 2 Q gives the set of possible next states; for each left bracket symbol < ∈ Σ +1 , the behaviour of the automaton is described by a function δ < : Q → 2 Q×Γ , which, for a given current state, provides a set of pairs (q, γ), with q ∈ Q and γ ∈ Γ , where each pair means that the automaton enters the state q and pushes γ onto the stack; for every right bracket symbol > ∈ Σ -1 , there is a function δ > : Q × (Γ ∪ {⊥}) → 2 Q specifying possible next states, assuming that the given stack symbol is popped from the stack (or that the stack is empty).

A configuration is a triple (q, w, x), with the current state q ∈ Q, remaining input w ∈ Σ * and stack contents x ∈ Γ * . Possible next configurations are defined as follows.

(q, cw, x)

A (q , w, x), c ∈ Σ 0 , q ∈ Q, q ∈ δ c (q) (q, <w, x) A (q , w, γx), < ∈ Σ +1 , q ∈ Q, (q , γ) ∈ δ < (q) (q, >w, sx) A (q , w, x), > ∈ Σ -1 , q ∈ Q, s ∈ Γ, q ∈ δ > (q, γ) (q, >w, ε) A (q , w, ε), > ∈ Σ -1 , q ∈ δ > (q, ⊥)
The language recognized by A is the set of all strings w ∈ Σ * , on which the automaton, having begun its computation in the configuration (q 0 , w, ε), eventually reaches a configuration of the form (q, ε, x), with q ∈ F and with any stack contents x ∈ Γ * (for well-nested inputs, the stack is empty at this point).

An NIDPDA is deterministic (DIDPDA), if there is a unique initial state and every transition provides exactly one action.

Von Braunmühl and Verbeek [START_REF] Braunmühl | Input driven languages are recognized in log n space[END_REF], proved that every n-state NIDPDA operating on well-nested strings can be transformed to a 2 n 2 -state DIDPDA. Alur and Madhusudan [START_REF] Alur | Visibly pushdown languages[END_REF] extended this construction to allow ill-nested inputs, so that a DIDPDA has 2 2n 2 states; in the worst case, 2 Ω(n 2 ) states are necessary.

The known closure results under Boolean operations, concatenation, star, reversal, quotient and edit distance neighbourhood are all valid for input-driven automata operating on ill-nested strings.

Insertion

The insertion operation is a binary operation on languages: ins(L, K) is the set of all strings obtained by taking any string from L and any position in this string, and inserting any string from K at that position.

ins(L, K) = { xyz | xz ∈ L, y ∈ K }
The question is: when both K and L are recognized by IDPDA, shall ins(L, K) always be recognized by an IDPDA? Provided that K does not contain any ill-nested strings, the answer is positive, established by the following effective construction.

Lemma 1. Let L be a language recognized by an NIDPDA B with the set of states Q and with a stack alphabet Γ . Let K be a set of well-nested strings, which is recognized by an NIDPDA A with the set of states P and with a stack alphabet Θ. Then, the language ins(L, K) is recognized by an NIDPDA with the set of states Q∪ Q∪(P ×Q), where Q = { q | q ∈ Q }, and with the stack alphabet Γ ∪ Θ.

Proof. The new automaton begins by simulating the computation of B in the states Q.

At any moment, while in a state q ∈ Q, it may nondeterministically guess that a substring accepted by A begins at the next symbol. If the next symbol is c ∈ Σ 0 , the new automaton may make a transition from q by c to a pair (p, q), where p is any state, to which A may go from its initial state p 0 by reading c. If the next symbol is a left bracket < ∈ Σ +1 , the new automaton may choose to go from q by the left bracket < to a pair (p, q), pushing θ, where A may go from p 0 to p by this bracket <, pushing θ.

Thus, the simulation of A on a substring begins. It proceeds in the states from P × Q, with the simulation carried out in the first component, whereas the state of B remembered in the second component remains unchanged. Whenever the simulating automaton is in a state (p, q) with p accepting, it may decide that the well-nested substring being inserted has now ended, and accordingly make simulate B's transition from the state q on the next input symbol. After that, the simulation continues as B in the states from Q.

This construction is optimal in the worst case, because of the recent result by Han et al. [START_REF] Han | State complexity of insertion[END_REF] for NFA. Han et al. [START_REF] Han | State complexity of insertion[END_REF] constructed a pair of witness languages, K and L, recognized by an m-state NFA and by an n-state, respectively, and proved that every NFA recognizing the language ins(L, K) must have at least mn + 2m states. Assuming that the partition of the alphabet is fixed, with all symbols in Σ 0 , and with no brackets, an NIDPDA cannot do anything more than an NFA, and for that reason, the lower bound by Han et al. [START_REF] Han | State complexity of insertion[END_REF] also applies to NIDPDA. This yields the following result.

Theorem 1. The state complexity of inserting a language recognized by an mstate NIDPDA into a language of well-nested strings recognized by an n-state NIDPDA is exactly mn + 2m.

On the other hand, if the strings being inserted are not required to be wellnested, then the closure property no longer holds, as shown in the next example.

Example 1. The following language is recognized by an input-driven automaton.

L = { < n > n | n 1 }
However, no input-driven automaton recognizes the language ins(L, <> * < * >).

Proof. If ins(L, <> * < * >) is recognized by some input-driven automaton, then so is its intersection with the regular language < + > + < + > + . The intersection ensures that the insertion is made exactly in the middle of a string

< n > n . ins(L, <> * < * >) ∩ < + > + < + > + = { < n+1 > i < j > n+1 | n, i, j 1 }
Let the latter intersection be recognized by a DIDPDA with a set of states Q. Let n = |Q| 2 + 1, and consider the accepting computation on the string < n > n < n > n . In the first half of this computation, that is, on the prefix < n > n , for every i ∈ {1, . . . , n}, let p i and q i be the states reached after reading < i and < n > n-i , respectively. When the automaton reads the (i + 1)-th left bracket in the state p i , it pushes the stack symbol s i = γ < (p i ), which is popped when reading the (n -i)-th right bracket in the state q j+1 , so that q j = δ > (q j+1 , s i ). There are |Q| 2 different pairs (p i , q i ), and therefore, for some i and j, these pairs coincide: (p i , q i ) = (p j , q j ), with i < j. Then the two segments of computation between p i+1 and p j and between q j and q i+1 , along with the stack symbols linking them to each other, can be cut, obtaining an accepting computation on the string < n+j-i > n+j-i < n > n , which does not belong to the language.

Deletion

The deletion operation is a binary operation on languages: del(L, K) is the set of all strings obtained by taking any string from L and removing any substring belonging to K from that string.

del(L, K) = { xz | ∃y ∈ K : xyz ∈ L }
If the set of strings being deleted consists of well-nested strings, there is the following closure result.

Lemma 2. Let a language L be recognized by an NIDPDA B with states Q and stack alphabet Γ . Let K be a language containing only well-nested strings, recognized by an NIDPDA A. Then, the language del(L, K) is recognized by an NIDPDA with the set of states Q ∪ Q, where Q = { q | q ∈ Q }, and with the stack alphabet Γ .

Proof. The new automaton first simulates B in the states from Q. At some point, while in some state q, it guesses that a string accepted by A has been deleted beginning from the next position. Let q ∈ Q be any such state of B, that there exists a well-nested string y, which is accepted by A, whereas B may read y beginning from the state q, and finish reading it in the state q . Then the simulating automaton may guess such a state q and continue its simulation, as if it is currently in the state q .

The construction is effective, because all pairs (q, q ) satisfying the above conditions can be determined by first constructing an IDPDA D q,q that recognizes the set of all strings y as defined above, and then applying the known emptiness test [START_REF] Alur | Adding nesting structure to words[END_REF] to this IDPDA.

If ill-nested strings may be deleted, then, as in the case of insertion, the family is no longer closed under this operation.

Example 2. The following language is recognized by an input-driven automaton.

L = { < m n n > m | m, n 1 }
However, no input-driven automaton recognizes the language del(L, * ).

Proof. If del(L, * ) is recognized by some input-driven automaton, then so is its intersection with the regular language < + + > + , which ensures that all double left brackets ( ) are erased.

del(L, * ) ∩ < + + > + = { < m i > m | m, i 1 }
If the latter intersection is recognized by a DIDPDA with a set of states Q, then let m = |Q|. Then, in the computation on < m m > m , the stack must be empty after reading the prefix < m m . In the last part of the computation, while reading the suffix > m , the automaton passes through a sequence of states p 0 , . . . , p m , behaving like a DFA, with every next state determined by a transition by the empty stack as p i+1 = δ > (p i , ⊥). Since m + 1 > |Q|, two of these states must coincide: p i = p j , with 0 i < j m. Then this segment of the computation can be cut out without affecting the acceptance, and the automaton accepts the string < m m > m-(j-i) , which is not in the language.

Square root

For a string of the form ww, the string w is its square root, denoted by √ ww = w. The square root of a language is defined as the set of square roots of all its applicable elements.

√ L = { w | ww ∈ L }
The regular languages are closed under this operation. Indeed, for every n-state DFA recognizing L, one can construct a DFA with n n states that computes the behaviour function of the original DFA on the string w: this is a function f w : Q → Q that maps each state q ∈ Q to the state reached by the DFA after reading w beginning from the state q. Denote by Q Q the set of all such functions. Then, the set of states of the constructed DFA is Q Q . This construction generalizes to input-driven automata, under the assumption that L contains only well-nested strings. Notably, in such a case, the language √ L also contains only well-nested strings.

Lemma 3. If a language L contains only well-nested strings, and is recognized by a DIDPDA with the set of states Q, then the language √ L is recognized by a DIDPDA with the set of states Q Q and with the stack alphabet

Σ +1 × Q Q .
The new DIDPDA processing w constructs the behaviour function [START_REF] Okhotin | Input-driven languages are linear conjunctive[END_REF][START_REF] Okhotin | State complexity of operations on input-driven pushdown automata[END_REF] of the original DIDPDA on w. This is one of the basic constructions for DIDPDA, based on the following observation: when a DIDPDA with a set of states Q processes a well-nested string w and begins in a state q, it finishes reading that string in some state f w (q), where f w : Q → Q is its behaviour function on w, and the stack is left untouched. Thus, f completely characterizes the behaviour of a DIDPDA on w. For any given DIDPDA A, it is possible to construct an n n -state DIDPDA, where n = |Q|, that reaches the end of an input w in a state representing the behaviour of A on the longest well-nested suffix of w. This construction is necessary for optimal constructions representing operations on DIDPDA [START_REF] Okhotin | State complexity of operations on input-driven pushdown automata[END_REF].

Proof (of Lemma 3). This is a known DIDPDA construction for the behaviour function f w : Q → Q of A on the input string w. Then the function f w • f w is its behaviour of A on ww, and the simulating automaton accepts in a state

f ∈ Q Q whenever (f • f )(q 0 ) ∈ F .
A matching lower bound for the state complexity of the square root on DFA is known. It immediately applies to DIDPDA, showing that n n is the exact complexity of the square root for this model as well.

Lemma 4 (Maslov [START_REF] Maslov | Estimates of the number of states of finite automata[END_REF]). For every n 1, there exists such an n-state DFA over a 3-symbol alphabet (equivalently, an n-state DIDPDA over the alphabet Σ +1 = Σ -1 = ∅, Σ 0 = {a, b, c}) that every DFA (as well as a DIDPDA) recognizing the language √ L requires at least n n states.

For NIDPDA, the state complexity of the square root is quite different. As to the authors' knowledge, the number of states in an NFA recognizing the square root of an n-state NFA is not yet known, and it is natural to establish it first.

Theorem 2. Square root of an n-state NFA is recognized by an n 3 -state NFA.

For every n, there is a language L n over a three-symbol alphabet, which is recognized by an n-state DFA, whereas every NFA recognizing

√ L n must have at least (n -1)(n -2)(n -3) states. Proof. Let A = (Σ, Q, Q 0 , δ, F ) be any n-state NFA. The NFA B recognizing L(A) uses the set of triples Q × Q × Q as its states.
In the beginning of its computation on a string w, it guesses the state p reached by A after reading w, remembers this state as the last component on the triple, and begins simulating two computations of A, one beginning from an initial state and the other beginning from p. Accordingly, its set of initial states is { (q 0 , p, p) | q 0 ∈ Q 0 , p ∈ Q }, and it uses the following transitions. δ (q, r, p), a = { (q , r , p) | q ∈ δ(q, a), r ∈ δ(r, a) } When B finishes reading w in a state (q, r, p), it has verified that A, upon reading w, can move from q 0 to q, as well as from p to r. If q = p, this confirms that A can move from q 0 to r upon reading ww, and if r is accepting, then B should accept its input string w. Accordingly, the set of accepting states of

B is { (p, r, p) | p ∈ Q, r ∈ F }.
Turning to the lower bound, the language L n is the standard "universal" witness language, as in Lemma 4. It is recognized by a DFA with the states {0, . . . , n -1}, and has the following property: for every function f : {0, . . . , n -1} → {0, . . . , n -1}, there is such a string x f , that, upon reading x f beginning from a state i, the DFA finishes reading it in the state f (i). The state 0 is initial and n -2 is accepting. Now the lower bound is proved using the standard fooling set method. Let (i, j, k) be a triple of states, with i, k ∈ {0, . . . , n-2}, j ∈ {1, . . . , n-3} and i = k. Define the string u i,j,k = x f , where f is a function defined by f (0) = i, f (j) = k and f (t) = n -1 for all remaining arguments. The other string is v i,j,k = x g , where g(i) = j, g(k) = n-2 and g(t) = n-1 for the rest of the arguments. Then, the concatenation u i,j,k v i,j,k maps the initial state to j, and j to the accepting state. This means that the square (u i,j,k v i,j,k ) 2 maps the initial state to the accepting state, and therefore u i,j,k v i,j,k belongs to L(A). On the other hand, for any two different pairs on this list, (u i,j,k , v i,j,k ) and (u i ,j ,k , v i ,j ,k ), at least one of the mismatched concatenations u i,j,k v i ,j ,k and u i ,j ,k v i,j,k is not in L(A). Then, every NFA recognizing the square root must have at least as many states as there are pairs in this fooling set, and there are (n-1)(n-2)(n-3) such pairs. The construction for NFA easily generalizes to NIDPDA, whereas the lower bound applies to NIDPDA as it is.

Theorem 3. Assume that a language L contains only well-nested strings, and let it be recognized by an NIDPDA with set of states Q, and with stack alphabet Γ . Then the language √ L is recognized by an NIDPDA with the set of states Q 3 and with the stack alphabet Γ 2 .

For every n, there is a language L n over an alphabet that consists of four neutral symbols, which is recognized by an n-state DFA, whereas every NIDPDA recognizing √ L n must have at least (n -1)(n -2)(n -3) states.

Thus, the state complexity of the square root has been established as n 3 -O(n 2 ) both for NFA and for NIDPDA. For the latter, the construction relies on all strings' being well-nested.

In the general case without the well-nestedness assumption, input-driven automata again demonstrate a non-closure.

Example 3. The following language is recognized by an input-driven automaton.

L = { > i < n > n < j | i, n, j 1 } ∪ { < m > m < n > n | m, n 1 }
Its square root has the following form.

√ L = { > n < n | n 1 } ∪ { < n > n | n 1 }
It is not recognized by any input-driven automaton, for any partition of the alphabet.

Propotional removals

For a string of even length, w = a 1 . . . a 2 , its first half, denoted by 1 2 w, is the string a 1 . . . a , obtained by discarding the second half of w. This operation is extended to languages element-wise, as follows. √ n ln n states. Later Domaratzki [START_REF] Domaratzki | State complexity of proportional removals[END_REF] has further investigated its state complexity, and Goč et al. [START_REF] Goč | Nondeterministic state complexity of proportional removals[END_REF] proved that for NFA, the state complexity of "one half" is Θ(n 2 ).

For input-driven automata, there is a construction somewhat similar to those used for finite automata. Unfortunately, it cannot anymore rely on determinizing unary NFA, and for that reason is much less efficient with respect to the number of states.

Lemma 5. For an n-state NIDPDA recognizing a language L, the well-nested subset of the language 1 2 (L) is recognized by an NIDPDA with 2 O(n 2 ) states. This time no assumptions are made on the well-nestedness of strings in L, but the construction produces an automaton that defines the intersection 1 2 L with the set of well-nested strings.

Proof. The states of the new automaton are of the form (q, q, p), where q is the state of the original automaton's ongoing simulation, q is the guessed state of the original automaton in the end of the simulation, whereas p is a state of a certain finite automaton.

For each state q i of the given input-driven automaton, there exists an NFA A i that accepts a string a if and only if there exists any string of length accepted by the input-driven automaton, beginning in the state q i with the empty stack. Such a finite automaton exists by Parikh's theorem, and is effectively obtained as follows. First, the NIDPDA is transformed to a grammar of size O(n 2 ). Then, the efficient construction for Parikh's theorem by Esparza et al. [START_REF] Esparza | Parikh's theorem: A simple and direct automaton construction[END_REF] is applied to this grammar, producing an NFA of size 2 O(n 2 ) .

Given the well-nested first half u of some string, the new automaton begins its computation in any state of the form (q 0 , q i , p (i) 0 ), where q 0 is the original automaton's initial state, q i is any of its states, and p (i) 0 is the initial state of the finite automaton A i . Then, the new automaton simulates the behaviour of the original automaton on u, along with running A i on the same string. In the end, the new automaton accepts if its first component reaches the state q i guessed in the beginning, while the simulated A i accepts the string.

The construction in Lemma 5 should be taken as a rough upper bound on the state complexity of one half. Improving this construction is proposed as an open problem.

If the exact value of 1 2 L is required, that is, without the intersection with the set of well-nested strings, then there is yet another non-closure result.

Example 4. The following language consists only of well-nested strings and is recognized by an input-driven automaton.

L = { < m > m < n (cc>) n cc | m, n 1 }
Proof. Each string is of length 2m+4n+2, and its first half is of length m+2n+1. This first half belongs to the set < * > * < * c if and only if m = n. For this reason, the set of first halves of strings in L, under intersection with the regular language < * > * < * c, has the following form.

1 2 L ∩ < * > * < * c = { < n > n < n c | n 1 }
The latter language is certainly not recognized by any input-driven automaton, and therefore neither is 1 2 L.

Scattered substrings

For each string w = a 1 . . . a n , any string a i1 . . . a i , with 1 i 1 < . . . < i n, is its scattered substring. Denote by sub(w) the set of all scattered substrings of w, and let sub(L) = w∈L sub(w) for a language L. By the Higman-Haines theorem [START_REF] Higman | Ordering by divisibility in abstract algebras[END_REF][START_REF] Haines | On free monoids partially ordered by embedding[END_REF], the language sub(L) is regular for an arbitrary language L, and can therefore be recognized by an IDPDA without paying attention to the bracket structure, by pushing and popping dummy stack symbols on the brackets.

For regular languages, the state complexity of scattered substrings is 2 Θ(n) [START_REF] Gruber | More on the size of Higman-Haines sets: effective constructions[END_REF][START_REF] Okhotin | On the state complexity of scattered substrings and superstrings[END_REF], with recent further results by Karandikar et al. [START_REF] Karandikar | On the state complexity of closures and interiors of regular languages with subwords and superwords[END_REF].

What is the state complexity of this operation for IDPDA? As proved by van Leeuwen [START_REF] Van Leeuven | Effective construction in well-partially-ordered free monoids[END_REF], for L given by a grammar, the language sub(L) is effectively regular. However, van Leeuwen's [START_REF] Van Leeuven | Effective construction in well-partially-ordered free monoids[END_REF] constructive proof does not include any estimation of the size of the regular language; it uses the finiteness of the basis to prove that the construction terminates. For that reason, no upper bound on the state complexity of scattered substrings for IDPDA is known.

1 2 (

 2 L) = { 1 2 w | w ∈ L, |w| is even } As reported bySeiferas and McNaughton [26], Yamada, Stearns and Hartmanis were the first to prove that the regular languages are closed under this operation. Maslov[START_REF] Maslov | Estimates of the number of states of finite automata[END_REF] determined its state complexity for DFA as 2 Θ( √ n log n) , relying on the known determinization of unary NFAs using e (1+o(1))


Oscar H Ibarra
email: ibarra@cs.ucsb.edu

Ian Mcquillan
email: mcquillan@cs.usask.ca

State Grammars with Stores

Keywords: grammars, reversal-bounded counters, automata models, matrix grammars

State grammars are context-free grammars where the productions have states associated with them, and can only be applied to a nonterminal if the current state matches the state in the production. Once states are added to grammars, it is natural to add various stores, similar to machine models. With such extensions, productions can only be applied if both the state and the value read from each store matches between the current sentential form and the production. Here, generative capacity results are presented for different derivation modes, with and without additional stores. In particular, with the standard derivation relation, it is shown that adding reversal-bounded counters does not increase the capacity, and states are enough. Also, state grammars with reversal-bounded counters that operate using leftmost derivations are shown to coincide with languages accepted by one-way machines with a pushdown and reversal-bounded counters, and these are surprisingly shown to be strictly weaker than state grammars with the standard derivation relation (and no counters). Complexity results of some decision problems involving state grammars with counters are also studied.

Introduction

State grammars were created by Kasai [START_REF] Kasai | An hierarchy between context-free and context-sensitive languages[END_REF], and have context-free grammar rules with additional state components. As originally defined, they consist of a set of nonterminals V , a set of terminals Σ, an initial nonterminal S ∈ V , a set of states Q, an initial state q 0 ∈ Q, and a set of productions P . Instead of normal contextfree productions of the form A → w, where A ∈ V, w ∈ (V ∪Σ) * , now productions are of the form (q, A) → (p, w), where q, p ∈ Q, and w was forced to be nonempty in Kasai's original formulation. Sentential forms are of the form (q, α) where q ∈ Q, α ∈ (V ∪Σ) * . A production is only applicable to a sentential form if the state of the production matches the state of the sentential form. The original derivation relation considered by Kasai (later called the leftish derivation relation in [START_REF] Moriya | On state-alternating context-free grammars[END_REF] which we will call it here as well), was as follows: (q, uAv) ⇒ lt (p, uwv) if (q, A) → (p, w) ∈ P , and A is the leftmost nonterminal in the sentential form that has a production that is applicable from the current state. A word is generated if there is some leftish derivation starting at the initial state and initial nonterminal that produces a word over Σ * . The family of languages generated by such systems with λ-free rules, denoted by L lt (λ-free-CFG-S), was shown to be equal to the family of context-sensitive languages [START_REF] Kasai | An hierarchy between context-free and context-sensitive languages[END_REF]. Later, it was shown that when including λ rules, the family produced, L lt (CFG-S), is equal to the family of recursively enumerable languages [START_REF] Salomaa | Matrix grammars with a leftmost restriction[END_REF].

The definition of state grammars was extended shortly afterwards by Moriya [START_REF] Moriya | Some remarks on state grammars and matrix grammars[END_REF] to also include a final state set F . Furthermore, he defined another derivation relation called the free interpretation, whereby any nonterminal can be rewritten that has a production defined on the current state, rather than the leftmost. With this derivation relation, the family of languages generated by state grammars, L(CFG-S), was proven to equal the languages generated by matrix grammars (or λ-free matrix grammars for λ-free state grammars) [START_REF] Dassow | Regulated Rewriting in Formal Language Theory[END_REF].

The notion of combining grammars with states is a powerful one. It is then easy to add various stores to grammars that operate like machine models. It can also enable the study of trade-offs between numbers of states, nonterminals, productions, and stores, relevant to the area of descriptional complexity. Changing the derivation relation and the rules allowed can also significantly change the families generated, obtaining many important language families as special cases.

In this paper, we will collate some of the existing generative capacity results on state grammars. In doing so, we provide a shorter alternative proof that state grammars (with the free interpretation) generate the same family as matrix grammars by using context-free grammars with regular control. A new derivation mode is defined where all nonterminals are rewritten from left-to-right until the last nonterminal, then this repeats starting again at the first nonterminal. State grammars with this mode are found to generate the recursively enumerable languages (or context-sensitive languages for λ-free grammars). We will then consider adding multiple reversal-bounded counters to state grammars (with the free interpretation) and find that this does not change the capacity beyond only having states. However, this system provides quite an easy way of describing languages. Furthermore, it is shown that leftmost derivations for state grammars are strictly weaker than leftmost derivations for state grammars with counters, which are then strictly weaker than state grammars with no counters using the free interpretation. Lastly, some complexity results are presented on state grammars with counters. Many proofs are omitted due to space constraints.

Preliminaries

Here, some notation used in the paper is presented; we refer to [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF] for an introductory treatment of automata and formal languages. We assume knowledge of deterministic and nondeterministic finite automata, context-free grammars, context-sensitive languages, and the recursively enumerable languages.

An alphabet Σ is a finite set of symbols, a word over Σ is a finite sequence of symbols a 1 • • • a n , n ≥ 0, a i ∈ Σ, 1 ≤ i ≤ n, and Σ * (respectively Σ + ) is the set of all words (non-empty words) over Σ. Then, Σ * contains the empty word, denoted by λ. Given a word w ∈ Σ * , the length of w is denoted by |w|, for a ∈ Σ, |w| a is the number of a's in w, and for subsets X of Σ, |w| X = a∈X |w| a . The set of letters occurring in w, alph(w

) = {a ∈ Σ | |w| a > 0}. Given Σ = {a 1 , . . . , a k }, the Parikh map of w is ψ(w) = (|w| a1 , . . . , |w| a k ), extended to languages L, ψ(L) = {ψ(w) | w ∈ L}. The commutative closure of L, comm(L) = {v ∈ Σ * | ψ(v) = ψ(w)
for some w ∈ L}. We will not define the notion of semilinear sets and languages here, but an equivalent definition is that a language L is semilinear if and only if it has the same commutative closure as some regular language [START_REF] Harrison | Introduction to Formal Language Theory[END_REF]. Given u, v ∈ Σ * , the shuffle of u and v, denoted by

u v is {u 1 v 1 • • • u n v n | u = u 1 u 2 • • • u n , v = v 1 v 2 • • • v n , u i , v i ∈ Σ * , 1 ≤ i ≤ n}.
The context-free languages are denoted by L(CFG), the linear languages are denoted by L(LG), the context-sensitive languages by L(CS), and the right linear (regular languages) are denoted by L(REG).

Moreover, we will discuss other families and grammars systems summarized in [START_REF] Dassow | Regulated Rewriting in Formal Language Theory[END_REF], such as matrix grammars. The languages generated by matrix grammars are denoted by L(M), and the languages generated by λ-free matrix grammars are denoted by L(λ-free-M).

Grammars with States

To start, we will formally define state grammars, following the notation of [START_REF] Moriya | Some remarks on state grammars and matrix grammars[END_REF] with final states. Definition 1. A state grammar (CFG-S), is a 7-tuple G = (V, Σ, P, S, Q, q 0 , F ), where V is the finite nonterminal alphabet, Σ is the finite terminal alphabet, S ∈ V is the initial nonterminal, Q is the finite set of states (V, Σ, Q are disjoint), q 0 ∈ Q is the initial state, F ⊆ Q is the set of final states, and P is a finite set of productions of the form:

(q, A) → (p, w),

where A ∈ V, w ∈ (V ∪Σ) * , q, p ∈ Q. The grammar is said to be linear (and is an LG-S) if, for all productions (q, A) → (p, w), w ∈ Σ * (V ∪ {λ})Σ * . The grammar is said to be right linear (and is a RLG-S) if, for all productions (q, A) → (p, w), w ∈ Σ * (V ∪ {λ}). In all cases, G is λ-free if all productions are to some (p, w) where w ∈ (V ∪ Σ) + . A sentential form of G is any element of Q×(V ∪Σ) * . Four different methods of derivation will be defined. They are as follows:

1. The free interpretation derivation relation is defined such that (q, uAv) ⇒ (p, uxv) if, (q, A) → (p, x) ∈ P , and u, v ∈ (V ∪ Σ) * . This is extended to the reflexive, transitive closure ⇒ * . The language generated by G is

L(G) = {w | (q 0 , S) ⇒ * (f, w), f ∈ F, w ∈ Σ * }.
2. The leftmost derivation relation is defined such that (q, uAv) ⇒ lm (p, uxv) if, (q, A) → (p, x) ∈ P , (q, uA) ⇒ (p, ux), and u ∈ Σ * . This is extended to the reflexive, transitive closure ⇒ * lm . The leftmost language generated by G is

L lm (G) = {w | (q 0 , S) ⇒ * lm (f, w), f ∈ F, w ∈ Σ * }. 3.
The leftish derivation relation is defined such that (q, uAv) ⇒ lt (p, uxv) if, (q, A) → (p, x) ∈ P , (q, uA) ⇒ (p, ux), and for all B ∈ alph(u) with B ∈ V , then there is no production from (q, B). This is extended to the reflexive, transitive closure ⇒ * lt . The leftish language generated by G is

L lt (G) = {w | (q 0 , S) ⇒ * lt (f, w), f ∈ F, w ∈ Σ * }.

The circular derivation relation is, for v

0 A 1 v 1 • • • A n v n , A i ∈ V, v i ∈ Σ * , 0 ≤ i ≤ n, (p 0 , v 0 A 1 v 1 A 2 • • • A n v n ) ⇒ • (p 1 , v 0 x 1 v 1 A 2 • • • A n v n ) ⇒ • (p 2 , v 0 x 1 v 1 x 2 v 2 A 3 • • • A n v n ) ⇒ • • • • ⇒ • (p n , v 0 x 1 v 1 x 2 v 2 • • • x n v n ),
where

(p i , A i+1 ) → (p i+1 , x i+1 ) ∈ P for all i, 0 ≤ i < n.
In this case, it is written

(p 0 , v 0 A 1 v 1 A 2 • • • A n v n ) ⇒ • (p n , v 0 x 1 v 1 x 2 v 2 • • • x n v n ).
This is extended to ⇒ * • , the reflexive, transitive closure of ⇒ • . Therefore, this relation rewrites all nonterminals from left-to-right, then repeats in a circular fashion. The circular language generated by G is

L • (G) = {w | (q 0 , S) ⇒ * • (f, w), f ∈ F, w ∈ Σ * }.
We also sometimes associate labels P Σ in bijective correspondence with P , and write u = ⇒ p v, if production p was applied from u to v (and similarly for the other derivation relations).

The family of languages generated by CFG-S grammars with the free interpretation (respectively the leftmost, leftish, and circular) derivation relation is denoted by L(CFG-S) (respectively L lm (CFG-S), L lt (CFG-S), L • (CFG-S)). For each of these families, we precede the family with λ-free to represent those language generated by λ-free systems; e.g. L • (λ-free-CFG-S). Similarly, replacing CFG-S with LG-S in these (or RLG-S) restricts the families to grammars where the rules are linear (or right linear).

Example 2. Let k ≥ 2, Σ = {a 1 , b 1 , . . . , a k , b k }, and G k = (V, Σ, P, S, Q, q 0 , F )
where Q = {q 0 , . . . , q k-1 }, F = {q 0 }, and P contains:

-(q 0 , S) → (q 0 , A 1 A 2 • • • A k ), -(q i-1 , A i ) → (q i , a i A i b i ) | (q i , a i b i ), for 1 ≤ i < k, -(q k-1 , A k ) → (q 0 , a k A k b k ) | (q 0 , a k b k ).
In any successful derivation using the free interpretation, states must follow a pattern in q 0 (q 0 • • • q k-1 ) + q 0 , and from q i-1 , only productions on A i can be applied, and they all must terminate on the last pass. Hence,

L(G k ) = {a n 1 b n 1 • • • a n k b n k | n > 0}.
For the first comparison, we see that the different derivation relations for linear and right linear grammars with states are the same. Proposition 3. The following are true:

-L(LG) = L(LG-S) = L lm (LG-S) = L lt (LG-S) = L • (LG-S), -L(REG) = L(RLG-S) = L lm (RLG-S) = L lt (RLG-S) = L • (RLG-S).
Proof. It is obvious that the method of derivation does not matter for linear and right linear grammars.

A linear grammar (resp., a right linear grammar) can easily be simulated by such a grammar with one state. The converse follows by creating nonterminals in V × Q. Then, for all productions of the form (q, A) → (p, uBv), q, p ∈ Q, A, B ∈ V, u, v ∈ Σ * , create a normal production (q, A) → u(p, B)v (ie. the state stays on the nonterminal; and for all terminating productions of the form (q, A) → (p, u), q, p ∈ Q, A ∈ V, u ∈ Σ * , create (q, A) → u if and only if p ∈ F . It is clear that the languages generated are the same.

The following was mentioned in [START_REF] Moriya | On state-alternating context-free grammars[END_REF], and it follows by considering the standard simulation of context-free grammars with pushdown automata, but using the state of the pushdown to simulate the state of the state grammar.

Proposition 4. L lm (CFG-S) = L(CFG).
As proven in [START_REF] Moriya | Some remarks on state grammars and matrix grammars[END_REF], the family of languages generated by matrix grammars (respectively λ-free matrix grammars) is equal to the family generated by state grammars (respectively λ-free state grammars) with the free interpretation. An alternate, shorter proof can also be demonstrated by showing equivalence of state grammars to context-free grammars with regular control [START_REF] Dassow | Regulated Rewriting in Formal Language Theory[END_REF]. It is known that such grammars are equivalent to matrix grammars [START_REF] Dassow | Regulated Rewriting in Formal Language Theory[END_REF]. Proposition 5. L(CFG-S) = L(M), and L(λ-free-CFG-S) = L(λ-free-M).

When circular derivations are used, then it will be seen next that CFG-S grammars already generate all recursively enumerable languages. We use the notion of a complete derivation tree t of a context-free grammar [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF], which is a tree where all nodes are labelled by either a nonterminal, a terminal, or λ, the root is labelled by the initial nonterminal, if a parent is labelled by A and its children are labelled by A 1 , . . . , A k from left to right, then

A → A 1 • • • A k is a production, if
a node is labelled by λ, then it is the only child of its parent, and all leaves are labelled by terminals. The yield of a derivation tree, yd(t), is the sequence of terminals obtained via a preorder traversal. Given such a tree t, level i is all nodes at distance i from the root, and the level-i word is the sequence of labels on the nodes of level i concatenated together from left to right. It is known that the set of yields of complete derivation trees of a grammar is exactly the language generated by the grammar [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF].

State grammars with the circular derivation will be shown equivalent to tree controlled grammars which are defined as follows. A tree controlled grammar is a tuple G = (V, Σ, P, S, R), where G = (V, Σ, P, S) is a CFG, and R is a regular language over V ∪ Σ. When considering context-free derivation trees in G , a restriction on the trees is used as follows: the language generated by G, L(G), is equal to {yd(t) | t is a complete derivation tree of G , for all levels i but the last, the level-i word is in R}.

Let L(TREE) (respectively L(λ-free-TREE)) be the family of languages generated by (respectively λ-free) tree controlled grammars. It is known that tree controlled grammars generate all recursively enumerable languages, and λ-free tree controlled grammars generate the context-sensitive languages [START_REF] Dassow | Regulated Rewriting in Formal Language Theory[END_REF]. Equivalence to tree controlled grammars therefore implies: Proposition 6. The following are true:

-L • (CFG-S) = L lt (CFG-S) = L(TREE) = L(RE), -L • (λ-free-CFG-S) = L lt (λ-free-CFG-S) = L(λ-free-TREE) = L(CS).
Hence, the following hierarchies are obtained:

Corollary 7.
The following are true:

-L(CFG) = L lm (CFG-S) L(CFG-S) = L(M) L • (CFG-S) = L lt (CFG-S) = L(RE), -L(λ-free-CFG) = L lm (λ-free-CFG-S)
L(λ-free-CFG-S) = L(λ-free-M) L • (λ-free-CFG-S) = L lt (λ-free-CFG-S) = L(CS).

State Grammars with Stores

Now that states are attached to grammars, it is quite natural to attach one or more stores as well, just like machine models. Then, store contents can be part of sentential forms just as states are with state grammars. For example, one could define context-free grammars with states plus a pushdown store. This would be represented with a tuple just like a CFG-S but with an additional word over the pushdown alphabet Γ and a bottom-of-pushdown marker Z 0 . In particular, the productions would be of the form (q, X, A) → (p, α, w), where q, p are states, A is a nonterminal, w is over the nonterminal and terminal alphabets, X is the topmost symbol of the pushdown, and α is the string to replace the topmost symbol of the pushdown. Sentential forms are therefore in Q × Γ + × (V ∪ Σ) * , and the derivation relation is defined in the obvious way. Here, we will attach multiple reversal-bounded counters as stores as they are defined with reversal-bounded counter machines [START_REF] Ibarra | Reversal-bounded multicounter machines and their decision problems[END_REF]. Explained briefly, a one-way k-counter machine is an NFA with k counters, each containing some non-negative integer, and the transition function can detect whether each counter is empty or not, and can increment, keep the same, or decrement each counter by one. Such a machine is r-reversal-bounded if the number of times each counter switches between non-decreasing and non-increasing is at most r. Then L(NCM) is the family of languages accepted by machines that are r-reversal-bounded k-counter machines, for some k, r ≥ 1.

Since grammars with states using either circular or leftish derivations already generate all recursively enumerable languages, we will not consider those derivation relations with stores.

Denote the set of all context-free grammars with states and some number of reversal-bounded counters by CFG-SC, and the languages they generate with the free interpretation and the leftmost derivation modes by L(CFG-SC) and L lm (CFG-SC) respectively. For each such grammar G = (V, Σ, P, S, Q, q 0 , F ) with k counters, productions are of the form (q, i 1 , . . . , i k , A) → (p, l 1 , . . . , l k , w), where p, q ∈ Q, i j ∈ {0, 1} (a production with i j = 0 is applied if and only if counter j is 0), l j ∈ {-1, 0, +1} (which changes the counter), A ∈ V, w ∈ (V ∪ Σ) * .

Example 8. Let G = (V, {a, b}, P, S, Q, q 0 , {q f }) be a CFG-SC with 2 counters accepting {w$w | |w| a = |w| b ≥ 0}, where P is as follows:

-(q 0 , 0, 0, S) → (q 0 , 0, 0, A 1 A 2 ), -(q 0 , i, j, A 1 ) → (q a , 1, 0, aA 1 ) | (q b , 0, 1, bA 1 ), for i, j ∈ {0, 1}, -(q a , i, j, A 2 ) → (q 0 , 0, 0, aA 2 ), (q b , i, j, A 2 ) → (q 0 , 0, 0, bA 2 ), for i, j ∈ {0, 1}, -(q 0 , i, i, A 1 ) → (q 1 , 0, 0, A 1 ), for i ∈ {0, 1}, -(q 1 , 1, 1, A 1 ) → (q 1 , -1, -1, A 1 ), -(q 1 , 0, 0, A 2 ) → (q 1 , 0, 0, λ), (q 1 , 0, 0, A 1 ) → (q f , 0, 0, $).

To start, G switches to (q 0 , 0, 0, A 1 A 2 ). Then the derivation repeatedly guesses either that A 1 derives an a or a b; if it guesses it derives an a, it switches to q a and increases the first counter, and then from q a , only A 2 can be rewritten and it must derive an a (similarly with the b case using q b and the second counter). Therefore, A 1 derives some sequence of terminals w and A 2 must derive the same sequence, and the first counter contains |w| a and the second contains |w| b . At any point while in state q 0 , G can switch to q 1 which repeatedly decreases both counters in parallel until both are verified to be zero at the same time, at which point both A 2 and A 1 are erased.

Before studying the generative capacity of CFG-SC, a definition is required. A CFG-SC G is in normal form if each counter makes exactly 1 reversal (once they decrease, they can no longer increase), and a terminal string is successfully generated when G enters a unique accepting state f and all the counters are zero. Moreover, at each step at most one counter is changed (i.e. , +1 or -1). We also assume that the state remembers when a counter enters a decreasing mode. So, e.g., when counter i enters the decreasing mode, the state remembers that from that point on, counter i can no longer increase. When another counter j enters the decreasing mode, the state now remembers that counters i and j can no longer increase, etc. Lemma 9. Let G be an CFG-SC. We can effectively construct a CFG-SC G in normal form such that L(G) = L(G ).

Hence, we may assume that a CFG-SC is in normal form.

Next, it will be seen that reversal-bounded counters do not increase the generative capacity. Proof. By [START_REF] Moriya | Some remarks on state grammars and matrix grammars[END_REF] (and Proposition 5), L(CFG-S) = L(M), and clearly L(CFG-S) ⊆ L(CFG-SC).

Let G be such a CFG-SC. Assume without loss of generality that G is in normal form, and it therefore has k 1-reversal bounded counters. Make a state grammar G (without counters) over Σ ∪ ∆ where

∆ = {c 1 , d 1 , • • • , c k , d k } are new symbols.
Then, G simulates G but, whenever it adds from counter i, it instead outputs terminal symbol c i , and whenever it decreases from counter i, it outputs d i . The states of G also verify that G starts by, for each counter i, simulating only productions associated with counter i being empty until it adds to the counter for the first time, then it simulates productions defined on counter i being positive (while outputting c i 's), then simulates productions on counter i being positive (while outputting d i 's), until some nondeterministically guessed spot after outputting some d i , where it guesses that the counter is now empty, and then it only simulates productions on counter i being empty while not outputting any more c i 's and d i 's. G operates in this fashion, as states were specifically marked in the normal form. Therefore, G operates just like G, where it simulates all of the counters, making sure that for each counter, all additions occur before any subtractions, but it does not do any of the counting. If one then restricted the derivations of G to those where the number of increases is the same as the number of decreases for each counter, then after erasing the letters of ∆, it would give L(G). But, consider the following regular language R = (c

1 d 1 ) * • • • (c k d k ) * Σ * ,
and the commutative closure of R, comm(R). Let h be a homomorphism that erases all letters of ∆ and fixes all letters of Σ. Then, h(L(G ) ∩ comm(R)) is exactly this language, where L(G ) ∩ comm(R) restricts words to only those that have the same number of c i 's as d i 's (and hence the same number of increases as decreases for each counter), and h erases the letters of ∆. Hence,

L(G) = h(L(G ) ∩ comm(R)).
Since G is a normal grammar with states, it can be converted to a matrix grammar G by Proposition 5. It is known that matrix grammars are closed under intersection with L(NCM) [START_REF] Stiebe | Slender matrix languages[END_REF] (there, they used closure under the BLIND multicounter languages which is equivalent to L(NCM) [START_REF] Greibach | Remarks on blind and partially blind one-way multicounter machines[END_REF]). Also, the commutative closure of every regular language is in L(NCM) [START_REF] Ibarra | The effect of end-markers on counter machines and commutativity[END_REF]. So L = L(G ) ∩ comm(R) is a language generated by a matrix grammar. Lastly, erasing all c i 's and d i 's with h gives L(G), and matrix grammars are closed under homomorphism [START_REF] Dassow | Regulated Rewriting in Formal Language Theory[END_REF]. Since this is a matrix grammar, it can be converted back to a normal state grammar by Proposition 5 generating the same language as L(G).

To note, in the proof above, in G, despite the counters being 1-reversal-bounded, productions can be applied to any nonterminal in the sentential form. Thus, some counter additions could occur when rewriting a nonterminal to the right of other nonterminals that get rewritten with a production that decreases. Hence, when intersecting with an L(NCM) language, it must not enforce that all c i 's occur before any d i 's.

The following corollary is true, since the results are known to be true for matrix grammars [START_REF] Hauschildt | Petri net algorithms in the theory of matrix grammars[END_REF].

Corollary 11. The following are true:

1. Every unary language generated by a CFG-SC is regular. 2. The emptiness problem for CFG-SC is decidable.

Next, we will study leftmost derivations of CFG-SC's. We will show that L lm (CFG-SC) = L(NPCM) L(CFG-SC), where NPCMs are one-way nondeterministic pushdown automata augmented by reversal-bounded counters [START_REF] Ibarra | Reversal-bounded multicounter machines and their decision problems[END_REF]. To help, we need the notion of a CFG with monotonic counters introduced in [START_REF] Ibarra | Grammatical characterizations of NPDAs and VPDAs with counters[END_REF]. This is a simpler model of grammars with counters that do not have states. At each step in the derivation, the counters can be incremented by 0 or +1, but not decremented. A derivation in this grammar starts with the counters having value zero. A terminal string w is in the language of the grammar if there is a derivation of w that ends with all counters having the same value.

A CFG with monotonic counters (CFG-MC) is a 5-tuple, G = (Σ, V, S, k, P ), where Σ is the set of terminals, V is the set of nonterminals, S ∈ V is the initial nonterminal, k is the number of monotonic counters, all are initially set to 0, and P is the set of rules of the form: A → (z, c 1 , . . . , c k ), where A ∈ V , z ∈ (V ∪ Σ) * and c i = 0 or +1.

The language defined is L(G) = {w | w ∈ Σ * , (S, 0, . . . , 0) ⇒ * (w, n, . . . , n) for some n ≥ 0}.

The following result was shown in [START_REF] Ibarra | Grammatical characterizations of NPDAs and VPDAs with counters[END_REF]:

Proposition 12. L(NPCM) is equal to the family of languages generated by CFG-MCs (using either the leftmost derivation relation or the normal derivation relation).

From this, the following can be shown:

Lemma 13. L(NPCM) = L lm (CFG-SC).
Proof. Every CFG-MC G with a leftmost derivation can be simulated by a CFG-SC with a leftmost derivation. It starts by simulating with one state. Then, before terminating, it guesses all counters are equal, decreases them all to verify, then terminates. Thus, L(NPCM) ⊆ L lm (CFG-SC). For the reverse containment, consider the standard simulation on a CFG with an NPDA with a leftmost derivation. This same construction can work with states while the counters of the CFG-SC can be simulated by the counters of the NPCM.

Lemma 14. L(NPCM) L(M).

Proof. It is clear that L(CFL) ⊆ L(M), it is known that L(M) is closed under intersection with L(NCM) [START_REF] Stiebe | Slender matrix languages[END_REF], and homomorphism [START_REF] Dassow | Regulated Rewriting in Formal Language Theory[END_REF]. Recently, a Chomsky-Schützenberger-like theorem was shown that demonstrates that every language in NPCM can be obtained by some Dyck language (which is context-free) intersected with an L(NCM) language, then mapped via a homomorphism [START_REF] Ibarra | Grammatical characterizations of NPDAs and VPDAs with counters[END_REF]. Therefore, L(NPCM) ⊆ L(M).

It is known that every NPCM language is semilinear [START_REF] Ibarra | Reversal-bounded multicounter machines and their decision problems[END_REF]. Now L(CFG-SC) = L(M) by Proposition 5. It known that matrix grammars can generate nonsemilinear languages, e.g., a matrix grammar can generate the non-semilinear language [START_REF] Dassow | Regulated Rewriting in Formal Language Theory[END_REF]

, L = {a n b m | 1 ≤ n < m ≤ 2 n }. It follows that L(NPCM) L(M).
Therefore, the following hierarchy exists by Propositions 4, 5, 6, 10 and Lemmas 13 and 14.

Proposition 15. The following is true:

L(CFG) = L lm (CFG-S) L lm (CFG-SC) = L(NPCM) L(CFG-S) = L(CFG-SC) = L(M) L lt (CFG-S) = L • (CFG-S) = L(RE).
Lastly, we study the emptiness problem for a restriction of CFG-SCs. A CFG-S G = (V, Σ, P, S, Q, q 0 , F ) is of index m, (m ≥ 1) if, for every w ∈ L(G), there exists some derivation (p 0 , α 0

) ⇒ (p 1 , α 1 ) ⇒ • • • ⇒ (p n , α n ), p 0 = q 0 , α 0 = S, p n ∈ F, α n = w with |α i | V ≤ m, for all 0 ≤ i ≤ n.
If it is index m for some m, then it is finite-index. This property is more general than requiring that every derivation of a word in the language has at most m nonterminals, a notion that is called uncontrolled index m, or uncontrolled finite-index. For contextfree grammars, the languages generated by uncontrolled finite-index grammars corresponds to pushdown automata with a reversal-bounded pushdown [START_REF] Ginsburg | Finite turn pushdown automata[END_REF], which cannot accept languages such as {a n b n | n > 0} * that can be generated by an index 2 grammar [START_REF] Rozenberg | On the effect of the finite index restriction on several families of grammars[END_REF]). Hence, finite-index CFG-S are quite general. Clearly, the definitions easily extend to m-index CFG-SC (finite-index CFG-SC).

Proposition 16. Let m, k ≥ 1 be fixed. The emptiness problem for m-index CFG-SC with at most k 1-reversal counters is decidable in polynomial time.

Proof. Let G be an m-index CFG-SC with at most k 1-reversal counters. We first construct from G a grammar G where all terminal symbols are mapped to λ. Clearly, L(G ) is empty if and only if L(G) is empty. Then all rules in G are of the form:

(q, i 1 , . . . , i k , A) → (p, l 1 , . . . , l k , u), where i j ∈ {0, 1}, l j ∈ {-1, 0, 1} for 1 ≤ j ≤ k, u is string of nonterminals of length at most m (possibly λ; there are no terminals used). Now from G , we construct an NCM M with k 1-reversal counters as follows: Its initial state is [q 0 , S], where q 0 is the initial state of G and S is the start nonterminal of G . The other states of M are of the form [q, w], where q is a state of G , and w is a string of at most m nonterminals (possibly λ).

Then M starts in state [q 0 , S] with all its k counters zero. A move of M is defined by: if G has a rule (q, i 1 , . . . , i k , A) → (p, l 1 , . . . , l k , v), i j ∈ {0, 1}, l j ∈ {-1, 0, 1} for 1 ≤ j ≤ k, then in M , for all strings xAy with |xAy| ≤ m and |xvy| ≤ m, create transitions from state [q, xAy] and counter status i 1 , . . . , i k on λ, that goes to state [p, xvy] and updates the counters by l 1 , . . . , l k . The accepting states of M are of the form [p, λ], where p is an accepting state of G .

Clearly, since G (and, hence, G ) is m-index and m is fixed, the size of M is polynomial in the size of G (hence, of G). Since M is an NCM with a fixed (k) number of 1-reversal counters and it is known that the emptiness problem for NCM with a fixed number of 1-reversal counters is decidable in polynomial time [START_REF] Gurari | The complexity of decision problems for finite-turn multicounter machines[END_REF], the result follows.

Note that if the index of G is not fixed, the size of M is no longer polynomial in the size of G (and, hence, of G). We also note that Proposition 16 can be generalized to hold for many m-index grammar systems with k 1-reversal counters (for fixed m and k).

Conclusions and Future Directions

State grammars were studied, and it was shown that with a new circular derivation relation, they generate all recursively enumerable languages. Then, using the free interpretation and the leftmost derivation relations, additional stores were added to state grammars; in particular, some number of reversal-bounded counters. When using the free interpretation derivation relation, the counters do not add any generative capacity, and only states are needed. When using leftmost derivations, the class coincides with the machine model NPCM (pushdown automata with reversal-bounded counters). This leads to the result that state grammars with counters and leftmost derivations are strictly weaker than state grammars with no counters and the free interpretation derivation relation.

There are many interesting problems of descriptional complexity that are open. For example, do state grammars form an infinite hierarchy with the number of states? We conjecture that in Example 2, for each k ≥ 2, it is impossible to generate L k with a state grammar with fewer than k states, which would form such a hierarchy.

Proposition 10 .

 10 L(CFG-S) = L(CFG-SC) = L(M).

The research of O. H. Ibarra was supported, in part, by NSF Grant CCF-1117708. The research of I. McQuillan was supported, in part, by Natural Sciences and Engineering Research Council of Canada Grant 2016-06172.


Enrico Formenti
email: enrico.formenti@unice.fr

Paolo Massazza
email: paolo.massazza@uninsubria.it

On the generation of 2-polyominoes

The class of 2-polyominoes contains all polyominoes P such that for any integer i, the first i columns of P consist of at most 2 polyominoes. We provide a decomposition that allows us to exploit suitable discrete dynamical systems to define an algorithm for generating all 2polyominoes of area n in constant amortized time and space O(n).

. . .

Introduction

A polyomino is a finite and connected union of unitary squares (cells) in the plane Z × Z, considered up to translations [START_REF] Golomb | Checker boards and polyominoes[END_REF]. The number of cells of a polyomino is its area. The problem of counting the number of polyominoes of area n (i.e. determining a closed formula for |Pol(n)|) is still open and the most used algorithm to generate Pol(n) runs in exponential time and uses exponential space [START_REF] Jensen | Enumerations of lattice animals and trees[END_REF]. Due to the space requirement, such algorithm has been used to compute |Pol(n)| only for n ≤ 56 [START_REF] Jensen | Counting polyominoes: A parallel implementation for cluster computing[END_REF]. So, it is interesting to study suitable representations of polyominoes that allow to design efficient generating algorithms with strict constraints on the space. To classify the polyominoes and to tackle some difficult questions about them, several subclasses have been introduced in literature. For instance, the class of convex polyominoes and its subclasses have been studied under different points of view [START_REF] Delest | Algebraic languages and polyominoes enumeration[END_REF][START_REF] Bousquet-Mélou | A method for the enumeration of various classes of columnconvex polygons[END_REF][START_REF] Castiglione | Reconstruction of L-convex polyominoes[END_REF][START_REF] Del Lungo | On the generation and enumeration of some classes of convex polyominoes[END_REF]. Recently, some efficient algorithms for the exhaustive generation by area of some subclasses of convex polyominoes have been presented [START_REF] Massazza | On the generation of convex polyominoes[END_REF][START_REF] Mantaci | From linear partitions to parallelogram polyominoes[END_REF][START_REF] Castiglione | An efficient algorithm for the generation of Z-convex polyominoes[END_REF][START_REF] Brocchi | On the exhaustive generation of k-convex polyominoes[END_REF].

The problem of efficiently generating non-convex polyominoes is particularly difficult. Indeed, no Constant Amortized Time (CAT) algorithm using space O(n) is known for the generation of Pol(n). In order to answer this question, we tackled some special cases in the hope of detecting all the conceptual obstacles and trying to remove them. Indeed, we are interested in the class Pol k (n) containing all polyominoes P of area n such that, for any i > 0, the first i columns of P are made of at most k polyominoes. A CAT algorithm for the exhaustive generation of Pol 1 (n) (called partially directed animals in [START_REF] Privman | Radii of gyration of fully and partially directed lattice animals[END_REF]), has been proposed in [START_REF] Formenti | From tetris to polyominoes generation[END_REF]. This paper provides a CAT algorithm that generates Pol 2 (n) using space O(n). Remark that Pol 2 (n) is a strictly new class which neither coincides with the class of partially directed animals with k sources (see Figure 1) nor with other known subclasses of polyominoes.

The algorithm is based on an idea that was already used for other exhaustive generation algorithms (for instance, [START_REF] Mantaci | From linear partitions to parallelogram polyominoes[END_REF][START_REF] Mantaci | On the exhaustive generation of plane partitions[END_REF][START_REF] Mantaci | An efficient algorithm for generating symmetric ice piles[END_REF]) and it is inspired by discrete a) b)

Fig. 1. a) a 2-polyomino corresponding to a partially directed animal with k +1 sources (k is the number of repetitions of the gray pattern). b) a partially directed animal with 3 sources which is not a 2-polyomino.

dynamical systems theory. Indeed, it proceeds to generate a polyomino column by column, and each column is uniquely decomposed into at most four parts, namely the skeleton and three regions. Each region corresponds to the state of a suitable dynamical system. Proving that the dynamical system is surjective and that it has one orbit grants exhaustive generation. Granting that the next state can be computed from the previous one in constant amortized time and in linear space leads to the result. This last step is accomplished through a careful choice of the data structure used to represent a polyomino. Because of the lack of space, most of the proofs and the pseudo-code have been omitted. They will appear in the long version of the paper.

Preliminaries

The area A(P ) of a polyomino P is the number of its cells. A polyomino can be seen as a (finite) sequence of columns. A column consists of a sequence of vertical segments separated by empty unit squares. A vertical segment is a sequence of unit cells q 1 , q 2 , . . . , q k that are in the same column and such that q i is edgeadjacent to q i+1 , for 1 ≤ i < k. The position of a cell is its y-coordinate. The position of the top (resp., bottom) cell of a segment s is denoted by Top(s) (resp., Bot(s)). We represent a segment s of a column by means of the pair (A(s) , Top(s)). Segments belonging to the same column are numbered from the top to the bottom, thus a column with p segments is simply a sequence of disjoint segments c = (s 1 , . . . , s p ), with Top(s i ) < Top(s i-1 ) -A(s i-1 ) -1 for 1 < i ≤ p. The area of c is A(c) = p i=1 A(s i ). Furthermore, the position of c is the position of its first segment, Top(c) = Top(s 1 ). Given a segment s and an integer j such that Top(s) > j ≥ Bot(s), we denote by s >j (resp., s ≤j ) the subsegment consisting of the cells of s with position greater than j (resp., smaller than or equal to j). The part of a column c that is above a position j is c >j (c ≥j , c ≤j and c <j are defined similarly). Segments can be ordered with respect to their position and their area. Definition 1 (< on segments). Let u and v be two segments. Then, one has u < v if and only if Top(u) > Top(v) or Top(u) = Top(v) and A(u) > A(v).

A total order on columns, denoted by ≺, can be easily obtained by extending <.

Definition 2 (≺ on columns). Let b = (s 1 , . . . , s p ) and c = (t 1 , . . . , t q ) be two columns. Then, one has b ≺ c if and only if either A(b) > A(c), or A(b) = A(c) and there exists m with 1 ≤ m ≤ min(p, q) such that s j = t j for all j < m and s m < t m .

Consider a polyomino P = (c 1 , . . . , c q ). We assume that the position of the bottom cell of the last segment of c 1 is 0. We indicate by P ≤i (resp., P i ) the sequence of the first i columns of P from the left (resp., the i-th column of P ), also called the i-prefix of P . We also write P <i for P ≤i-1 . The area of P is A(P ) = w i=1 A(P i ) where w is the number of columns of P . From here on, Pol(n) denotes the set of the polyominoes of area n.

Definition 3. (The class Pol k (n)) Let k > 0.
The class of k-polyominoes of area n, Pol k (n), contains all P ∈ Pol(n) such that, for all i with 1 ≤ i < w, P ≤i consists of at most k polyominoes, where w is the number of columns of P .

The class Pol 1 (n) corresponds to the class of partially directed animals [START_REF] Redner | Size and shape of directed lattice animals[END_REF][START_REF] Privman | Radii of gyration of fully and partially directed lattice animals[END_REF][START_REF] Privman | Exact solution of the partially directed compact lattice animal model[END_REF], for which a CAT generation algorithm has been provided in [START_REF] Formenti | From tetris to polyominoes generation[END_REF]. Here, we are interested into an efficient exhaustive generation algorithm for the class Pol 2 (n).

Two segments s and t are adjacent if they belong to adjacent columns and there exists at least one cell of s that is edge-adjacent to a cell of t. The set LAdj(s) of left-adjacencies of a segment s contains the positions of the cells of s that are edge-adjacent to some cells of segments in P i-1 . A segment s is ldetached if LAdj(s) = ∅, whereas it is l-adjacent if LAdj(s) = ∅. A column that does not contain l-detached segments is called l-detached-free. The segment of P i immediately above (resp., below) s is s ↑ (resp., s ↓ ). If s is l-detached then ↓ s (resp., ↑ s) indicates the first (resp., last) segment v in P i-1 such that Top(v) < Bot(s) (resp., Bot(v) > Top(s)). Otherwise, if s is l-adjacent then ↑ s (resp., ↓ s) indicates the segment in P i-1 that has a cell in the position min(LAdj(s)) (resp., max(LAdj(s))). For any segment s of P i , Con(s) is the largest polyomino comprised in P ≤i that contains s. Let P ≤i consist of two polyominoes U and V . Then, U ↑ (resp., V ↑ ) indicates the upper extreme of U (resp., V ) in P i , that is, the first segment u ∈ U (resp., v ∈ V ) of

P i such that u ↑ ∈ V or u ↓ ∈ V (resp., v ↑ ∈ U or v ↓ ∈ U ). Analogously, U ↓ (resp., V ↓ ) denotes the lower extreme of U (resp., V ) in P i that is, the last segment u ∈ U (resp., v ∈ V ) of P i such that u ↑ ∈ V or u ↓ ∈ V (resp., v ↑ ∈ U or v ↓ ∈ U ). If U ↓ = U ↑
then U has only one extreme in P i , denoted by U . We say that U and V are independent if both U and V have only one extreme in P i (U is above V or vice versa), see Cases b), c) and d) of Fig. 2. Similarly, U includes V if V ↑ is immediately below U ↑ and V ↓ is immediately above U ↓ , see Cases f ) and g) of Fig. 2. Thus, U and V are enclosing if U includes V or vice versa.

A segment s of P i is a bridge if P <i consists of two polyominoes Ū and V and s is l-adjacent to two segments v and v ↓ , which are extremes of Ū and V , respectively. The distance Dist(s) of an extreme s is the number of empty unit squares that separate s from the nearest segment t ∈ {s ↓ , s ↑ } with Con(t) = Con(s). In other words, Dist(s) + 2 is the area of the smallest bridge that can join s and t. The vertical distance of two segments s, t with Bot(s) ≥ Top(t) is d(s, t) = Bot(s) -Top(t) -1. If P ≤i consists of two distinct polyominoes U and V , we also set Dist(U, V ) = min{Dist(s)|s is an extreme of U }.

Notation: from here on, P ≤i (resp., P <i ) denotes an i-prefix (resp., (i -1)prefix) of a polyomino in Pol 2 (n). A bar over a segment indicates that it is a bridge, s. Given a sequence S of i -1 columns and a column c, the operation | of column concatenation (left associative) produces a new sequence S = S|c with i columns. A column c is compatible with P i-1 , denoted by c P i-1 , if and only if P <i |c is the i-prefix of a polyomino in Pol 2 (n). Obviously, one has c P i-1 if and only if P <i |c ∈ Pol 2 (n) or there exists a column d such that P <i |c|d ∈ Pol 2 (n). We denote by Comp(P <i , k, n) the set of columns of area k that are compat-

P<i Pi a) V U P<i Pi b) V ŪP<i Pi c) U V Ū V P<i Pi d) V U ŪP<i Pi f ) V U ↓ U ↑ Ū P<i Pi e) Ū V P<i Pi g) V ↑ U ↑ V ↓ U ↓
(b) =                    () if P <i ∈ Pol (s) if b contains only one bridge s (s, t) if b contains two bridges s, t (s, s ↓ ) if P <i |b = U ∪ V, s = U , s ↓ = V (s, s ↓ , s ↓↓ ) if P <i |b = U ∪ V, s = U ↑ , s ↓ = V , s ↓↓ = U ↓ (s, s ↓ , u, u ↓ ) if P <i |b = U ∪ V, s = U ↑ , s ↓ = V ↑ , u = V ↓ , u ↓ = U ↓ where U ↑ , U ↓ , V ↑ , V ↓ , V , U are l-adjacent extremes of b (with no bridges).
Notice that if b contains a bridge t then it does not contain an l-adjacent extreme s with Con(t) = Con(s) (otherwise P <i consists of at least three polyominoes). For any b ∈ Comp(P <i , k, n) such that Ske(b) = () one has Ske(b) ∈ Comp(P <i , h, n) for a suitable integer h ≤ k. The set Sk(P <i , k, n) = {c ∈ Comp(P <i , j, n)|j ≤ k ∧ Ske(c) = c} contains the skeletons of area at most k that are compatible with P i-1 . Obviously, one has

Comp(P <i , k, n) = b∈Sk(P<i,j,n) [b] . Notice that Sk(P <i , j, n) = ∅ if Sk(P <i , j + 1, n) \ Sk(P <i , j, n) = ∅.
We define a total order on Sk(P <i , k, n) as follows. (resp., s < v), or s = v (resp., s = v) and t < w (resp., t < w); -b = (s, t, u), c = (v, w, z) and either s < v, or s = v and t < w, or s = v, t = w and u < z; -b = (q, r, s, t), c = (u, v, w, z) and either q < u, or q = u and r < v, or q = u, r = v and s < w, or q = u, r = v, s = w and t < z;

In Sect. 4, polyominoes of Pol 2 (n) are generated column by column. All the columns that are compatible with P i-1 are generated according to the following ordering.

(Ske(b) is null) b ≺ c; (Ske(b) is (s) or (s, t) or (s, t, u)) either b ↑ ≺ c ↑ , or b ↑ = c ↑ ∧ b ↓ ≺ c ↓ ; (Ske(b) is (s, t) or (s, t, u, v)) either b ↑ ≺ c ↑ , or b ↑ = c ↑ ∧ b ≺ c , or b ↑ = c ↑ ∧ b = c ∧ b ↓ ≺ c ↓ ;
3 Dynamical systems for regions A split move may occur only in a position j ∈ [Bot(s) , Top(s)) of a segment s. In this case, s is split into s >j and s ≤j . The segment s >j stays in place whereas s ≤j is shifted e positions downwards, where e is the smallest integer such that the resulting region R satisfies Conditions 1-3 above, see Fig. Proof. (outline) Let s, s ↓ and s ↓↓ be the last three segments of R. If R does not contain an l-detached segment then a shift move on s ↓ is always defined. Otherwise, if s (resp., s ↓ ) is l-detached then a shift move on s (resp., s ↓ ) is defined. Lastly, if s ↓↓ is l-detached then s can always be shifted. Remark that in general several moves are possible in R. However, we are interested in the one occurring in the lowest position. This leads to the following: Definition 9 (Grand ancestor). Let R be a region of b and suppose that j = min(Mcr(P <i |b, R, δ)) is defined. The grand ancestor GA(P <i |b, R, δ) of R is a region G delimited as R and such that A(G) = A(R), G is identical to R in the positions above j -1, G admits a move at j and for all other regions R satisfying the previous properties, it holds G ≺ R (possibly, G = R ). The lowest position where a move may occur in a segment s is characterized in the following Lemma.

Lemma 2. Let s be a segment of a region R of b and let j be the lowest position of s such that j ∈ Mcr(P <i |b, R, δ). Then,

j =      Bot(s) or 1 + min(LAdj(s)) or Top(s) if δ = 0, Bot(s) or 1 + Bot(s) if δ > 0 and s is l-adjacent, Bot(s) or Top(s) if δ > 0 and s is l-detached,
We point out that the data structure described in Sect. 4.1 allows (in time O(1)) both to find the lowest position j where a move may occur in a segment s, and to make the move at j. Furthermore, the grand ancestor can be effectively computed by exploiting Lemmas 1 and 2. Indeed, one can easily prove the following:

Lemma 3. Given a region R = (s 1 , . . . , s m ) of b, let s h be the segment with a cell in position j = min(Mcr(P <i |b, R, δ)). Then, GA(P <i |b, R, δ) = (s 1 , . . . , s h-1 )• (s , s ↓ ) where Top(s ) = Top(s h ) and

A(s ) = A(s h ) + w -1, A s ↓ = 1, Top s ↓ = Top( ↓ s h ) if G, A(s ) = A(s h ) + w, s ↓ = otherwise,
where w = m k=h+1 A(s k ) and G holds if and only if s h is l-detached, d(s h-1 , s h ) > δ and d(s h , v) -w > δ, where v is the segment below s m (if any).

Given two regions R and R , write R ⇒ R if and only if R is obtained by making a move in R. Moreover, R j ⇒ R if j ∈ Mcr(P <i |b, R, δ) and the move at the position j of R produces the region R .

At this point we are ready to define a discrete dynamical system f P<i|b,δ that takes in input a region R of b and changes its content, producing a region R such that R ≺ R unless the input region contains no moves.

Definition 10 (The dynamical system over regions). Given a region R of b, let j = min(Mcr(P <i |b, R, δ)) and define

f P<i|b,δ (R) = R if j = ⊥ and GA(P <i |b, R, δ) j ⇒ R R otherwise.
Let R = (s 1 , . . . , s m ) be a region of a column b. Then, RC(Ske(b), R, δ) denotes the set of all sequences G of segments, with A(G) = A(R), such that one can replace R with G obtaining a different column b with b P i-1 . Remark that RC(Ske(b), R, δ) is finite and totally ordered by ≺. We call initial region its minimum element, denoted R min . Indeed, R min is delimited by u and v, where u = s ↑ 1 and v ↑ = s m (they both can be null), and it contains at most two segments s and s ↓ with

Top(s ) = Bot(u)-2 if u = ∧(Bot( ↓ u) < Bot(u)-1∨w > d(u, ( ↓ u) ↓ )∨δ > 0) Bot(s ) = Top(( ↓ u) ↓ ) if u = ∧(w ≤ d(u, ( ↓ u) ↓ )∧Bot( ↓ u) ≥ Bot(u)-1∧δ = 0) Bot(s ) = f if u = ∧ δ = 0 Bot(s ) = f + δ + 1 if u = ∧ δ > 0 (1)
where w = m k=1 A(s k ) and f is the position of the first segment of P i-1 . Moreover, A(s ) = w and s ↓ = unless δ > 0 and u = , in which case one has A(s ) = w -1, A s ↓ = 1 and Top s ↓ = Top(z). The following lemma proves that f P<i|b,δ starts in an initial region and eventually ends.

(P <i |b • a • b , a, δ) = ∅ it holds a ≺ f P<i|b,δ (a); 2. RC(Ske(b), R, δ) = n∈N f n P<i|b,δ (R min ), where f n P<i|b,δ (R min ) corresponds to f P<i|b,δ (f n-1 P<i|b,δ (R min )), with f 0 P<i|b,δ (R min ) = R min .
In other words, the previous lemma grants that if one wants to exhaustively generate all possible regions, it is enough to effectively simulate the dynamical system f P<i|b,δ . There will be neither missing regions nor repetitions.

Exhaustive generation of Pol 2 (n)

An inductive approach is used. Given i, k ∈ N and a skeleton b ∈ Sk(P <i , k, n) (where P <i is the current prefix), suppose that all the polyominoes Q ∈ Pol 2 (n) with Q ≤i = P <i |c have been already generated, for all columns c such that A(c) = k and Ske(c) = b , where b ∈ Sk(P <i , k, n) and b b. We proceed by generating all the columns c ∈ Comp(P <i , k, n) ∩ [b] and then, for each c, we (recursively) generate all the polyominoes Q ∈ Pol 2 (n) with Q ≤i = P <i |c. Thus, the problem is reduced to design an efficient algorithm for generating the set Comp(P <i , k, n). To this aim, we propose an algorithm that works in two steps:

1. an outer loop that generates all skeletons b in Sk(P <i , k, n); 2. an inner loop that, for each b, generates all colums c ∈ Comp

(P <i , k, n)∩[b] .
The algorithm is a smart combination of two main iterators (functions that run through ordered sequences), one for skeletons and one for columns. The pseudocode of all iterators and functions will appear in the long version of this paper. Here we briefly describe how they works.

The iterator NextSkel(P <i , k, b, δ) takes P <i , an integer k, a skeleton b ∈ Sk(P <i , k, δ) and δ, and returns the smallest skeleton larger than b in Sk(P <i , k, δ). The function is based on Def. 7 and exploits different iterators for different types of skeletons. More precisely, the first skeleton b init is either null (if P <i ∈ Pol), or it consists of a suitable bridge b init = (s) with A(s) = k (if P <i consists of two polyominoes U and V with Dist(U, V ) + 2 < k), or it consists of two suitable extremes, b init = (s, t) with A(s) = k -1 and A(t) = 1 (if Dist(U, V ) + 2 > k). If b init = () then, for any k ≥ 0, one has Sk(P <i , k, δ) = {()} and we are done. Otherwise, the successor b of a non-null skeleton b depends on the number of its segments and on their types -either bridges or extremes, see Def. 4. Indeed, if b = (s) then b is obtained by using an iterator NextBridge that works as follows. If b is not the last skeleton consisting of one bridge, then b is obtained either by shifting s (if after a shift by e positions downwards s remains a bridgee is always 1 if P i-1 contains only two extremes), or by replacing s with a smaller bridge t, with A( t) = A(s) -1, placed in the highest possible position (i.e. t is l-adjacent to the first two extremes e and e ↓ in P i-1 with d(e, e ↓ ) + 2 ≤ A( t)). Otherwise, b is the last element in the ordered sequence of skeletons consisting of one bridge, and b should be the smallest skeleton consisting of two bridges of total area k. A function InitBridges is used for this purpose. Otherwise, one can not place two bridges of total area k in column i (because the number of cells k is not sufficient or P i-1 has only two extremes or it has three extremes e 1 , e 2 and e 3 with A(e 2 ) = 2), and then b should be the smallest skeleton consisting of two l-adjacent extremes of total area k. Similarly, if b = (s, t) then b is obtained either by using an iterator NextTwoExtremes (if b is not the greatest skeleton consisting of two extremes), or a function InitThreeExtremes.

NextTwoExtremes either shifts t, or it shifts s and places t in the highest possible position below s (if t can not be shifted), or it constructs the smallest skeleton comprising two extremes s and t with A(s ) = A(s) -1 and A(t ) = A(t) + 1 (if neither t nor s can be shifted), or it constructs the smallest skeleton of area k -1 that consists of two extremes (if A(s ) = 1). Otherwise, b is greatest skeleton consisting of two extremes and b is the smallest skeleton with three l-adjacent extremes of total area k. The remaining cases b = (s, t), b = (s, t, u) and b = (s, t, u, v) are treated similarly.

In addition to the previous iterators, an iterator Next is used to run through a sequence of regions. Next(R, δ) takes a region R and returns a region R obtained according to the dynamical system provided in Def. 10. Furthermore, let Init(Ske(b), r, m, δ) be the function that takes a skeleton, the type r of the region (northern, central, southern), an integer m and δ, and returns the smallest region of type r and area m, see the characterization NextCol works similarly also in the cases where three regions can be present (skeletons of type (s, t) or (s, t, u, v)). Lastly, if NextCol(P <i , c, δ, n) = ⊥ then c consists of the smallest skeleton larger than Ske(c), with A(c ) = k, which is returned by NextSkel(P <i , k, Ske(c), δ). The correctness of all the iterators directly follows from their definition and from the order on skeletons and on columns.

The data structure

We represent P ≤i by an array of i records, one per column. The record for the i-th column is a tuple (L, U ↑ , U ↓ , V ↑ , V ↓ , R 1 , R 2 , R 3 ). The first field L is a doubly-linked list for the sequence of segments representing the column (as many nodes as segments), then we have four links to the nodes associated with the extremes of the column (at least one is non-null). Lastly, we have three links to the last node of each region (at least one is non-null). Each node of the list L corresponds to a segment s (represented by (A(s) , Top(s))) and contains five entries (s, l 1 , l 2 , l 3 , l 4 ), where l 1 is a link to the preceding node (for s ↑ ), l 2 is the link to the next node (for s ↓ ), l 3 and l 4 are the links to the nodes (in the list representing the preceding column) associated with ↑ s and ↓ s, respectively. Given a region R of P i , by Lemma 1 the move in the position min(Mcr(P ≤i ,R , δ)) regards one of the last three segments of R. Notice that this data structure allows the execution of any move (either Shift or Split) in time O(1) (Lemmas 2 and 3). Figure 5 illustrates the data structure associated with a polyomino.

U ↑ U ↓ V ↑ V ↓ R 1 R 2 R 3 (3,18) (2,13) (2,10) (1,6) (2,3)
U ↑ U ↓ V ↑ V ↓ R 1 R 2 R

Complexity

The execution of the algorithm that generates Pol 2 (n) is represented by a tree T (n) where an internal node v at level i corresponds to a suitable i-prefix P ≤i . Furthermore, the children of v correspond to the (i + 1)-prefixes P ≤i |c, for all c in k Comp(P ≤i , k, n). Then, the complexity of v, denoted by C(v),

Conclusions

This paper further deepens the new approach to polyominoes generation started in [START_REF] Formenti | From tetris to polyominoes generation[END_REF], by presenting a new CAT generation algorithm for Pol 2 (n), which takes linear space. We strongly believe that all conceptual obstacles have been detected and that our approach might lead to a CAT algorithm working in linear space for the generation of the full set Pol(n).

Fig. 2 .

 2 Fig. 2. Columns, compatibility and skeletons (represented by gray cells). ible with P i-1 . Bridges and l-adjacent extremes are called special segments. They determine a unique decomposition of b into regions, and they form the so-called skeleton of b. The skeleton of a column b ∈ Comp(P <i , k, n), denoted by Ske(b), is either the column consisting of the bridges in b (if any), or the column containing all l-adjacent extremes in b (if b does not contain a bridge and P <i ∈ Pol). Definition 4. Let b ∈ Comp(P <i , k, n). Then, the skeleton of b is the column

Definition 5 .

 5 The northern (resp., central, southern) region of b = (s 1 , . . . , s q ) is denoted by b ↑ (resp., b , b ↓ ) and it is defined as follows (Ske(b) to the left): (): b ↑ = b; (s m ): b ↑ = (s 1 , . . . , s m-1 ) and b ↓ = (s m+1 , . . . , s q ); (s m , sp ): b ↑ = (s 1 , . . . , s m-1 ), b = (s m+1 , . . . , s p-1 ), b ↓ = (s p+1 , . . . , s q ); (s m , s m+1 ): b ↑ = (s 1 , . . . , s m-1 ), b ↓ = (s m+2 , . . . , s q ); (s m , s m+1 , s m+2 ): b ↑ = (s 1 , . . . , s m ), b ↓ = (s m+3 , . . . , s q ); (s m , s m+1 , s p , s p+1 ): b ↑ = (s 1 , . . . , s m-1 ), b = (s m+2 , . . . , s p-1 ), b ↓ = (s p+2 , . . . , s q ); Remark that if s and t are l-adjacent segments belonging to the same region then Con(s) = Con(t). The notion of skeleton induces an equivalence relation on Comp(P <i , k, n). Definition 6 ( ). Let b, c ∈ Comp(P <i , k, n). Then, one has b c if and only if Ske(b) = Ske(c).

Definition 7 (

 7 on Sk(P <i , k, n)). Let b, c ∈ Sk(P <i , k, n). Then, one has b c if and only if one of the following conditions holds: -|b| < |c|, ( i.e. b contains less segments than c); -b contains a bridge whereas c does not; -b = (s), c = ( t) and s < t; -b = (s, t) (resp., b = (s, t)), c = (v, w) (resp., c = (v, w)) and either s < v

Definition 8 (

 8 < on columns). Let b, c ∈ Comp(P <i , k, n). Then, one has b < c iff Ske(b) Ske(c) or Ske(b) = Ske(c) and one of the following holds:

  Given a column b, its skeleton Ske(b) uniquely identifies the regions b ↑ , b ↓ and b . Recall that a region of b is a particular subsequence of b consisting of consecutive segments delimited by special segments in Ske(b). In each region, we are going to use specific dynamical systems such that their current state represents a list of segments that when completed with the skeleton produces a compatible column. All compatible columns can be built in this way. Given an i-prefix P <i |b, with h = A(b) (1 ≤ h ≤ n -A(P <i )), and a segment s of a region R of b, a move at j ∈ [Bot(s) , Top(s)] is an operation which rearranges the cells of R while respecting a constraint (expressed by a value δ ≥ 0) regarding the creation of l-detached segments. More precisely, if δ = 0 then no new l-detached segment can be created (because an l-detached segment is already present in b, or the number of remaining cells is not sufficient to create a bridge in the next column, that is, n -A(P <i |b) < 3, or Ske(b) contains at least two l-adjacent extremes), whereas δ > 0 allows the creation of a new l-detached segment with distance at most δ only if b is l-detached free (moreover, Ske(b) should not contain l-adjacent extremes and δ + 2 = n -A(P <i |b)). Two types of moves are devised, namely shift and split, and both output a region R such that R ≺ R . Notice that, since Ske(b) ∈ Comp(P <i , j, n) (with j ≤ h), any rearrangement R of the cells of R such that 1. R is l-detached free if δ = 0, 2. no cell of R becomes edge-adjacent to a segment of Ske(b), 3. if δ > 0 then R contains at most one l-detached segment s and Dist(s ) ≤ δ produces a column b ∈ Comp(P <i , h, n). A shift move may occur only in the position j = Top(s) of a segment s. It has the effect of shifting the segment s by e positions downwards, where e is the smallest integer such that the resulting region satisfies Conditions 1-3 above, see Fig.2(left). Possibly, s and s ↓ are joined (if s ↓ ∈ Ske(b)). If such an e does not exist, then the move is undefined.

  2 (center). Possibly, s ≤j and s ↓ are joined (if s ↓ ∈ Ske(b)), see Fig. 2 (right). Denote by Mcr(P <i |b, R, δ) the set of the positions where a move occurs on a segment of R. The following lemma relates the non-emptyness of Mcr(P <i |b, R, δ) to the number of segments in R. Lemma 1. Let R be a region of b. If R contains at least three segments, then Mcr(P <i |b, R, δ) = ∅.

Fig. 3 .

 3 Fig. 3. Examples of shift (left) and split moves (center and right).

Fig. 4 .

 4 Fig. 4. Examples of grand ancestor (gray cells are those redeployed, δ = 4).

Lemma 4 .

 4 Consider an i-prefix P <i |b of a polyomino in Pol 2 (n) and a region R of b, b = b • R • b . Then, one has 1. for all a ∈ RC(Ske(b), R, δ) such that Mcr

  (1) for R min . The iterator NextCol(P <i , c, δ, n) takes a column c ∈ Comp(P <i , k, n) and δ, and returns the smallest column c in Comp(P <i , k, n) such that c < c and Ske(c) = Ske(c ). NextCol works by distinguishing six cases, depending on Ske(c). Let DF(b) = 1 if the column b is l-detached free, 0 otherwise. The simplest case is when Ske(c) is null, hence c = c ↑ . Here, the next column is simply Next(c, δ). Now, consider the case Ske(c) = (s) where c has at most two regions (the case Ske(c) = (s, t, u) is treated in the same way). One has c = c ↑ • (s) • c ↓ . So, if c ↑ = then c is either (s) • b where b = Next(c ↓ , δ) (if b = ⊥), or ⊥ (if b = ⊥). Otherwise, one has c ↑ = and c is either c ↑ • (s) • e (if e = Next(c ↓ , DF(c ↑ ) • δ) = ⊥) or e • (s) • e where e = Next(c ↑ , δ)) and e = Init(P <i , south, A(c ↓ ) , Ske(c), DF(e)•δ) (if e = ⊥ and e = ⊥), or (if e = e = ⊥) Init(P <i , north, A c ↑ -1, Ske(c), δ) • (s)• Init(P <i , south, A(c ↓ ) + 1, Ske(c), 0).

Fig. 5 .

 5 Fig. 5. Two columns (left) and the associated data structure (right).

  is the time taken to generate the set k Comp(P ≤i , k, n) (as many columns as children of v), withC(v) = O(1) if v is a leaf. Since f (n) = O(g(n)) and g(n) = |Pol 2 (n)|, where f (n) (resp., g(n)) is the number of internal nodes (resp., leaves) of T (n), it follows that the algorithm is CAT if one proves that C(T (n)) = O(|T (n)|), where C(T (n)) = v∈T (n) C(v). Indeed, it holds the following result. Theorem 1. C(T (n)) = O(|T (n)|).