Bruno Guillon
email: guillonb@di.unimi.it

Giovanni Pighizzini
email: pighizzini@di.unimi.it

Luca Prigioniero
email: prigioniero@di.unimi.it

Non-Self-Embedding Grammars, Constant Height Pushdown Automata, and Limited Automata

Non-self-embedding grammars are a restriction of contextfree grammars which does not allow to describe recursive structures and, hence, which characterizes only the class of regular languages. A double exponential gap in size between non-self-embedding grammars and deterministic finite automata is known. The same size gap is also known from constant height pushdown automata and 1-limited automata to equivalent deterministic finite automata. Constant height pushdown automata and 1-limited automata are compared with non-self-embedding grammars. It is proved that non-self-embedding grammars and constant height pushdown automata are polynomially related in size. However, they can be exponentially larger than 1-limited automata.

Introduction

It is well-known that the extra capability of context-free grammars with respect to regular ones is that of describing recursive structures as, for instance, nested parentheses, arithmetic expressions, typical programming language constructs. In terms of recognizing devices, this capability is implemented in the pushdown store, which is used to extend finite automata in order to make the resulting model, namely pushdown automata, equivalent to context-free grammars.

To emphasize this capability, in one of his pioneering papers, Chomsky investigated the self-embedding property [START_REF] Chomsky | A note on phrase structure grammars[END_REF]: a context-free grammar is self-embedding if it contains a useful variable A which, in some sentential form, is able to reproduce itself surrounded by two nonempty strings α and β, in symbols A =⇒ αAβ. Roughly speaking, this means that the variable A is "truly" recursive. He proved that, among all context-free grammars, only self-embedding ones can generate nonregular languages.

Hence, non-self-embedding grammars are no more powerful than finite automata.

The relationships between the description sizes of non-self-embedding grammars and equivalent finite automata have been investigated in [START_REF] Anselmo | Finite automata and non-selfembedding grammars[END_REF] and [START_REF] Pighizzini | Non-self-embedding grammars and descriptional complexity[END_REF]. In the worst case, the size of a deterministic automaton equivalent to a given non-self-embedding grammar is doubly exponential in the size of the grammar. The gap reduces to a simple exponential in the case of nondeterministic automata.

Other formal models characterizing the class of regular languages and exhibiting gaps of the same order with respect to deterministic and nondeterministic automata have been investigated in the literature. Two of them are constant height pushdown automata and 1-limited automata. The aim of this paper is to study the size relationships between non-self-embedding grammars and these models.

Constant height pushdown automata are standard nondeterministic pushdown automata where the amount of available pushdown store is fixed. Hence, the number of their possible configurations is finite. This implies that they are no more powerful than finite automata. The exponential and double exponential gaps from constant height pushdown automata to nondeterministic and deterministic automata have been proved in [START_REF] Geffert | More concise representation of regular languages by automata and regular expressions[END_REF]. Furthermore, in [START_REF] Bednárová | Removing nondeterminism in constant height pushdown automata[END_REF] the authors showed the interesting result that also the gap from nondeterministic and deterministic constant height pushdown automata is double exponential. We can observe that both nonself-embedding grammars and constant height pushdown automata are restrictions of the corresponding general models, where true recursions are not possible. In the first part of the paper we compare these two models by proving that they are polynomially related in size.

In the second part of the paper, we turn our attention to the size relationships between 1-limited automata and non-self-embedding grammars.

For each integer d > 0, a d-limited automaton is a one-tape nondetermin-2 Draft: Wednesday 10 th May, 2023 14:05 stic Turing machine which is allowed to rewrite the content of each tape cell only in the first d visits. These models have been introduced by Hibbard in 1967, who proved that for each d ≥ 2 they characterize contextfree languages [START_REF] Hibbard | A generalization of context-free determinism[END_REF]. Furthermore, as shown in [START_REF] Wagner | Computational Complexity[END_REF]Thm. 12.1], 1-limited automata are equivalent to finite automata. This equivalence has been investigated from the descriptional complexity point of view in [START_REF] Pighizzini | Limited automata and regular languages[END_REF], by proving exponential and double exponential gaps from 1-limited automata to nondeterministic and deterministic finite automata, respectively. Our main result is a construction transforming each non-self-embedding grammar into an equivalent 1-limited automaton of polynomial size. For the converse transformation, we show that an exponential size is necessary. Indeed, we prove a stronger result by exhibiting, for each n > 0, a language L n accepted by a two-way automaton with O(n) states, which requires exponentially many states to be accepted even by an unresticted pushdown automaton. From the cost of the conversion of 1-limited automata into equivalent nondeterministic automata, it turns out that for the conversion of 1-limited automata into non-self-embedding grammars an exponential size is also sufficient. Given a set S, we denote by #S its cardinality, and by 2 S the family of all its subsets. We assume the reader familiar with notions from formal languages and automata theory, in particular with the fundamental variants of finite automata (1dfas, 1nfas, 2dfas, 2nfas, for short, where 1 and 2 mean one-way and two-way, respectively, and d and n mean deterministic and nondeterministic, respectively). For further details see, e.g., [START_REF] Hopcroft | Introduction to automata theory, languages, and computation[END_REF]. The empty word is denoted by ε. Given a word u ∈ Σ * , we denote by |u| its length. For every h ≥ 0, Σ h denotes the set of words of length h over the alphabet Σ, while Σ + denotes the set of all nonempty words over Σ.

For two-way devices operating on a tape (e.g., 2nfa), we use the special symbols and not belonging to the input alphabet, respectively called the left and the right endmarkers, that surround the input word.

Context-free Grammars

Given a context-free grammar (cfg, for short) G = V, Σ, P, S , we denote by L (G) the language generated by G. The relations ⇒ and =⇒ are defined in the usual way. The production graph of G is a directed graph which has V as vertex set and contains an edge from A to B if and only if there is a production A → αBβ in P , for A, B ∈ V and some α, β ∈

(V ∪ Σ) * .
Definition 1 (nse grammars). Let G = V, Σ, P, S be a context-free grammar. A variable A ∈ V is said to be self-embedded when there are

two strings α, β ∈ (V ∪Σ) + such that A =⇒ αAβ. The grammar G is self- embedding if it contains at least one self-embedded variable, otherwise G is non-self-embedding ( nse, for short).
Chomsky proved that nse grammars generate only regular languages, i.e., they are no more powerful than finite automata [START_REF] Chomsky | On certain formal properties of grammars[END_REF][START_REF] Chomsky | A note on phrase structure grammars[END_REF]. As shown in [START_REF] Anselmo | Finite automata and non-selfembedding grammars[END_REF],

given a grammar G it is possible to decide in polynomial time whether or not it is nse.

Pushdown automata

A pushdown automaton (pda) is usually obtained from a nondeterministic finite automaton by adding a pushdown store, containing symbols from a pushdown alphabet Γ . Following [START_REF] Geffert | More concise representation of regular languages by automata and regular expressions[END_REF][START_REF] Bednárová | Removing nondeterminism in constant height pushdown automata[END_REF], we consider pdas in the following form, where the transitions manipulating the pushdown store are clearly distinguished from those reading the input tape. Furthermore, we consider a restriction of the model in which the capacity of the pushdown store is bounded by some constant h ∈ N.

Definition 2 (Pushdown automata of constant height). A pushdown automaton of height

h ( h-pda) is a tuple A = Q, Σ, Γ, δ, q 0 , F, h
where Q is the set of states, q 0 ∈ Q is the initial state, F ⊆ Q is the set of final states, Σ is the input alphabet, Γ is the pushdown alphabet, h ∈ N is the pushdown height bound, and δ ⊆ Q × ({ε} ∪ Σ ∪ {-, +}Γ ) is the transition relation with the following meaning:

(i) (p, ε, q) ∈ δ: A can reach the state q from the state p without using the input tape nor the pushdown store (these transitions are also called εmoves);

(ii) (p, a, q) ∈ δ: A can reach the state q from the state p by reading the symbol a from the input but without using the pushdown store;

(iii) (p, -X, q) ∈ δ: if the symbol on the top of the pushdown store is X, A can reach the state q from the state p by popping the symbol X, not using the input tape;

(iv) (p, +X, q) ∈ δ: if the number of symbols contained in the pushdown store is less than h, A can reach the state q from the state p by pushing the symbol X on top of the pushdown store, without using the input tape.

The model accepts an input word w ∈ Σ * , if, starting from the initial state q 0 with an empty pushdown store, it can eventually reach an accepting state q f ∈ F , after having read all the input symbols.

Without the restriction on the pushdown height, the model is equivalent to classical pushdown automata, while preserving comparable size 5 Draft: Wednesday 10 th May, 2023 14:05 (namely, translations both ways have at most polynomial costs, see [START_REF] Bednárová | Removing nondeterminism in constant height pushdown automata[END_REF]).

By contrast, 0-pdas are exactly nfas, since they can never push symbols.

1-limited automata

One-limited automata (1-las, for short) extend 2-way finite automata by providing the ability to overwrite each tape cell at its first visit by the head. This extension does not increase the expressiveness of the model. However, they can be significantly smaller than equivalent finite automata.

For instance, the size gaps from 1-las to nfas and dfas are exponential and double exponential, respectively [START_REF] Pighizzini | Limited automata and regular languages[END_REF], while 2nfas can be exponentially larger than deterministic 1-las even in the unary case [START_REF] Pighizzini | Limited Automata and Unary Languages[END_REF].

Definition 3 (1-limited automata). A 1-limited automaton is a tuple A = Q, Σ, Γ, δ, q 0 , F , where Q, Σ, q 0 , F are defined as for 2nfas, Γ is a finite working alphabet such that Σ ⊂ Γ , and δ : Q × Γ → 2 Q×Γ ×{-1,+1} is the transition function, where Γ denotes the set Γ ∪ { , } with , / ∈ Γ the left and the right endmarkers.

In one move, according to δ and to the current state, A reads a symbol from the tape, changes its state, replaces the symbol just read by a new symbol, and moves its head to one position backward or forward. However, replacing symbols is subject to some restrictions, which, essentially, allow to modify the content of a cell during the first visits only. Formally, symbols from Σ shall be replaced by symbols from Γ \ Σ, while symbols from Γ \ Σ are never overwritten. In particular, at any time, both special symbols and occur exactly once on the tape and exactly at the respective left and right boundaries. Acceptance for 1-las can be defined in several ways, for instance we can say that a 1-la A accepts an input word if, starting from the left endmarker in the initial state, the computation eventually reaches the right endmarker in an accepting state. The language accepted by A is denoted by L (A).

6 Draft: Wednesday 10 th May, 2023 14:05

Size of models

For each model under consideration, we evaluate its size as the total number of symbols used to define it. Hence, as a measure for the size of a grammar G = V, Σ, P, S , we consider the total number of symbols used to specify it, defined as Symb(G) = (A→α)∈P (2 + |α|) (cf. [START_REF] Kelemenová | Complexity of normal form grammars[END_REF]). The size of an h-pda A = Q, Σ, Γ, δ, q 0 , F, h is given by some polynomial in #Q, #Γ and h. Finally, the size of a 1-la A = Q, Σ, Γ, δ, q 0 , F is given by a polynomial in #Q and #Γ .

nse grammars versus h-pdas

In this section we prove that nse grammars and h-pdas are polynomially related in size.

From nse grammars to h-pdas

In [START_REF] Anselmo | Finite automata and non-selfembedding grammars[END_REF], the authors showed that nse grammars admit a particular form based on a decomposition into finitely many simpler grammars, that will be now recalled.

First of all, we remind the reader that a grammar is said right-linear (resp. left-linear), if each production is either of the form A → wB (resp.

A → Bw), or of the form A → w, for some A, B ∈ V and w ∈ Σ * . It is well known that right-or left-linear grammars generate exactly the class of regular languages.

Given two cfgs

G 1 = V 1 , Σ 1 , P 1 , S 1 and G 2 = V 2 , Σ 2 , P 2 , S 2 with V 1 ∩ V 2 = ∅, the ⊕-composition of G 1 and G 2 is the grammar G 1 ⊕ G 2 = V, Σ, P, S , where V = V 1 ∪ V 2 , Σ = (Σ 1 \ V 2 ) ∪ Σ 2 , P = P 1 ∪ P 2 ,
and S = S 1 . Intuitively, the grammar G 1 ⊕ G 2 generates all the strings which can be obtained by replacing in any string

w ∈ L (G 1 ) each sym- bol A ∈ Σ 1 ∩ V 2 with a string in the language L G 2|A derived in G 2 from the variable A (notice that the definition of G 1 ⊕ G 2 does not depend on the start symbol S 2 of G 2 ).
The ⊕-composition is associative, and preserves the property of being non-self-embedding [START_REF] Anselmo | Finite automata and non-selfembedding grammars[END_REF]. The decomposition 7 Draft: Wednesday 10 th May, 2023 14:05 presented in the following result was obtained in [1, Theorem 2], while its size is discussed in [START_REF] Pighizzini | Non-self-embedding grammars and descriptional complexity[END_REF].

Theorem 1. For each nse grammar G there exist

g grammars G 1 , G 2 , . . . , G g such that G = G 1 ⊕ G 2 ⊕ • • • ⊕ G g ,
where each G i is either left-or rightlinear. Furthermore the sum of sizes of G i 's is linear in the size of G.

Studying the relationships between nse grammars and pdas, in [START_REF] Anselmo | Finite automata and non-selfembedding grammars[END_REF] the authors claimed that from any nse grammar in canonical normal form (namely with productions Proof. First of all, we observe that from each left-linear grammar G = V, Σ, P, S we can obtain an equivalent right-linear grammar G = V ∪ {S }, Σ, P , S whose size is linear in the size of G, with one more variable S / ∈ V and the following productions:

A → aγ or A → γ, A ∈ V , a ∈ Σ and γ ∈ V * ),
-B → w, for each S → Bw in P , -B → wA, for each A → Bw in P (including S → Bw),
-S → wA, for each A → w in P .

We point out that if we apply the above transformation to the grammar G | Ŝ = V, Σ, P, Ŝ obtained by changing the initial symbol of G into Ŝ ∈ V , then the set of productions of the resulting grammar could be different from P .

G iA , with A ∈ V i ,
where G iA is equivalent to the grammar G i|A = V i , Σ i , P i , A . It can be verified that the size of the resulting grammar G is at most quadratic in the size of G.

Theorem 2. Let G = V, Σ, P, S be an nse grammar such that G =

G 1 ⊕ G 2 ⊕ • • • ⊕ G g ,
where each G i is right-linear. Then there is an equivalent pda of polynomial size such that the height of the pushdown store is bounded by a polynomial in g.

Proof. First of all, as in the construction presented in [START_REF] Anselmo | Finite automata and non-selfembedding grammars[END_REF], we show that, for i = 1, . . . , g, if a variable A ∈ V i derives a string xα by a leftmost derivation, i.e., A =⇒ lm xα, where x is the longest prefix of xα consisting only of terminal symbols, then the length of α is linear in g -i. More precisely, we claim that |α| ≤ K(g -i) + 1, where K is the maximum length of production right-hand sides. We are going to prove this claim by induction on g -i.

For g -i = 0, the only possible derivations from a variable A ∈ V g have the forms A =⇒ x and A =⇒ xB, with x ∈ Σ * and B ∈ V g . Then the claim immediately follows.

For g -i > 0, the claim is trivial in case α = ε. Otherwise, suppose that the first production used in the derivation under consideration is A →

X 1 X 2 • • • X s , i.e., A =⇒ X 1 X 2 • • • X s =⇒ lm α 1 α 2 • • • α s = xα where X k ∈ Σ ∪ g j=i V j and X k =⇒ lm α k , k = 1, . . . , s. Let , 1 ≤ ≤ s,
be the smallest index such that α contains at least one variable. Hence, 9 Draft: Wednesday 10 th May, 2023 14:05

we can write x = x x where x = α 1 α 2 • • • α -1 , x α = α , α k = X k for k = + 1, . . . , s, and α = α X +1 • • • X s .
If X ∈ V j , with j > i, then, by induction hypothesis, |α | ≤ K(g -

j) + 1. Hence |α| ≤ K(g -j) + 1 + s -< K(g -i) + 1 due to the fact that s -< K.
Since G i is right-linear, the case X ∈ V i could occur only when = s, thus implying that

X 1 X 2 • • • X s-1 is

From h-pdas to nse grammars

Let A be an h-pda. We first show that, modulo acceptance of the empty word, with only a polynomial increase in the size we can transform it in a special form.

Lemma 2. For each h-pda A = Q, Σ, Γ, δ, q 0 , F, h there exists an hpda A = Q , Σ, Γ , δ , q -, {q + }, h and a mapping h : Γ → {1, . . . , h} such that:

-L (A ) = L (A) \ {ε}; -A has polynomial size with respect to A; every nontrivial computation path of A starting and ending with the same pushdown content and never popping off symbols under this level, consumes one input letter, i.e., during such a computation, at least one transition from Q × Σ × Q is performed; -A accepts with empty pushdown; each symbol X ∈ Γ can appear on the pushdown only at height h(X).

Proof. First, we create two new states q -and q + , intuitively the new initial and unique final states, respectively, and we add transitions (q -, ε, q 0 ) and (p, ε, q + ) for each p ∈ F . Furthermore, in order to empty the pushdown store at the end of the accepting computations, we add the transition (q + , -X, q + ) for each X ∈ Γ . We denote by Q the set Q ∪ {q -, q + }.

Second, by extending Q to Q × {0, . . . , h}, we can suppose that each state stores the current height of the pushdown as second component.

After this change, we set (q -, 0) as initial state and (q + , 0) as unique final state (as a consequence, acceptance is necessarily made with empty pushdown). We then set Γ = Γ ×{1, . . . , h} and we modify the transitions in such a way that a symbol (γ, i) ∈ Γ can be pushed only from a state in Q × {i -1}, i.e., only at pushdown height i. The mapping h is then defined on Γ as the projection over the second component. Now, for each state (p, i) ∈ Q × {0, . . . , h}, we define the set E (p,i) of states (q, i) which are accessible from (p, i) by using only transitions in

(Q × {i, . . . , h}) × ({ε} ∪ {-+}Γ ) × (Q × {i, . . . ,

h}).

The restriction to states from Q × {i, . . . , h} ensures that the considered computation paths can never pop off symbols under their initial level, while the restriction on the set of actions forbid any reading of the input. We first replace such computations by a single ε-move. This can be achieved as follows:

we create a transition ((p, i), ε, (q, i)) for each (q, i) ∈ E (p,i) ;

we add a new state component storing an element in {push, pop, read} that saves the last operation performed during the computation (with the natural meaning, ε-moves being not considered as operations) and we forbid transitions of the form (p, -X, q) whenever the last operation is push. (For simplicity, the newly-introduced component will not appear in the end of the proof.) After such transformation, the only computations that starts and ends with same pushdown content and without popping off symbols under the corresponding level, are necessarily sequences of ε-moves. Hence, each set E (p,i) , which is kept unchanged by the above transformation, is now equal to {(q, i) | (p, i) * (q, i) using only ε-moves}.

We finally proceed to the elimination of ε-moves, using classical techniques. First, we consider the set E (q -,0) of states that are accessible from the initial configuration through a sequence of ε-moves. For each state (p, 0) ∈ E (q -,0) and each transition ((p, 0), ψ, (r, i)) with ψ = ε, we create a transition ((q -, 0), ψ, (r, i)). We then remove every ε-moves from q -, i.e., every transition of the form ((q -, 0), ε, (p, 0)). As a consequence, the empty word cannot be accepted by the resulting h-pda.

However, since every computation of A accepting a nonempty word should perform a transition of the form ((p, 0), ψ, (r, i)) with ψ = ε at some point, our transformation preserves acceptance of nonempty words.

Lastly, the remaining ε-moves are eliminated as follows. For each transition of the form (p, ψ, q) with ψ = ε and each r ∈ E q , we create the transition (p, ψ, r). We finally remove all remaining ε-moves.

The complete construction has polynomial cost and the resulting hpda A accepts an input word if and only if the word is nonempty and Furthermore, pAq =⇒ x if and only if besides the above conditions [START_REF] Anselmo | Finite automata and non-selfembedding grammars[END_REF] and ( 3), the following condition (stronger than (2)) is satisfied:

(2 ) in all configurations of the computation path C others than the first and the last one, the pushdown is higher than in the first and in the last configuration of C.

Proof. First of all, we are going to prove that for all x, p, q, A as in the statement of the lemma, [pAq] =⇒ x implies (1), [START_REF] Bednárová | Removing nondeterminism in constant height pushdown automata[END_REF], and (3), while pAq =⇒ x implies (1), (2 ), and (3). We proceed by induction on the length k ≥ 1

of the derivation [pAq] k =⇒ x or pAq k =⇒ x.
For k = 1, there are no derivations [pAq]

1 =⇒ x, while pAq 1 =⇒ x
implies that x is a terminal symbol and (p, x, q) ∈ δ (the production is of the form (i)), from which (1), [START_REF] Bednárová | Removing nondeterminism in constant height pushdown automata[END_REF], and (3) trivially follow.

Suppose now k > 1. The first production applied in a derivation

[pAq] k =⇒
x is either of the form (iii) or of the form (iv). In the first case we have

[pAq] =⇒ pAr [rAq] k-1 =⇒ x, pAr k =⇒ x , [rAq] k =⇒ x , for some r ∈ Q, 1 ≤ k , k < k, k +k = k-1, x , x ∈ Σ + such that x x = x.
Using the induction hypothesis, we can find two computations path C and C , from state p to r and from state r to q, respectively, with A at the top of the pushdown at the beginning and at the end, such that the pushdown is never popped under its level at the beginning of these paths, and consuming the factors x and x , respectively. By concatenating these two paths, we find the path C satisfying in (1), (2), and (3).

If [pAq] =⇒ pAq k-1
=⇒ x (i.e., the first production applied is of the form (iv)), ( 1), (2), and (3) follow from the induction hypothesis applied to the derivation pAq

k-1 =⇒ x.
We now consider a derivation pAq k =⇒ x, with k > 1. The first step can only be of the form (ii), namely pAq =⇒ [p Xq ] k-1 =⇒ x. From the induction hypothesis, there is a computation path C from state p to state q which starts and ends with X at the top of the pushdown, never popping off the pushdown under the initial level, and consuming x from 14 Draft: Wednesday 10 th May, 2023 14:05 the input tape. From a configuration with state p and A at the top of the pushdown, A can start a computation path which pushes X, simulates C , and finally pops X off the pushdown. While simulating C the pushdown always contains the symbol X over A. Hence, it is higher than in the first and in the last configuration of C. This proves (1), [START_REF] Bednárová | Removing nondeterminism in constant height pushdown automata[END_REF], and (3).

To prove the converse implications, we proceed by induction on the length k of the computation path C satisfying conditions (1), ( 2 For k > 1 we consider two cases. First we suppose that C satisfies (1), ( 2), ( 3), but does not satisfy [START_REF] Bednárová | Removing nondeterminism in constant height pushdown automata[END_REF]. We decompose C in two shorter paths C and C that are delimited by the first configuration which is reached in C with the same pushdown height as at the beginning and at the end of C. These two paths satisfy (1), ( 2), (3). Furthermore, C satisfies also [START_REF] Bednárová | Removing nondeterminism in constant height pushdown automata[END_REF]. By the induction hypothesis, we get that pAr =⇒ x , [rAq] =⇒ x , where r is the state reached at the end of C and x x = x. Using production (iv) we obtain the derivation [pAq] =⇒ pAr [rAq] =⇒ x x = x.

If C satisfies (1), (2 ), and (3), then it should start in state p with a push of a symbol X moving in a state p , ends after a pop of the same symbol X from a state q to state q, where the symbol X is never popped off the pushdown in between. The path C , consisting of k -2 moves, obtained by removing from C the first and the last move, consumes the same input string x which is consumed by C. From the induction hypothesis, we obtain that [p Xq ] =⇒ x and, considering (ii), pAq =⇒ [p Xq ] =⇒ x. Furthermore, by (iv), we also obtain [pAq] =⇒ x.

From Lemma 3, considering production (v), we can easily conclude that the grammar G so defined is equivalent to the given pda A.

Lemma 4. The above defined grammar G is non-self-embedding.

Proof. From productions (ii), we observe that h(A ) > h(A) for any possible variable p A q or [p A q ] that can appear in a sentential form from a variable pAq . Hence, each variable pAq is not self-embedded. Now, we consider any variable of the form [pAq]. We observe that in each derivation [pAq]

+ =⇒ α[pAq]β, α, β ∈ (V ∪Σ) * , the occurence of [pAq]
on the right-hand side can be obtained only if, each time the rightmost variable is rewritten, productions of the form (iii) are used. Hence, the string β must be empty. This allows us to conclude that each [pAq] is not self-embedded.

By combining the previous results, we obtain: Theorem 3. For each h-pda there exists an equivalent nse grammar of polynomial size.

Proof. From Lemmas 2 to 4, from an h-pda A we can obtain an nse grammar G of polynomial size generating L (A) \ {ε}. In case ε ∈ L (A), in order to make G equivalent to A we add the production S → ε.

As a consequence of Theorems 2 and 3, we obtain that each nse grammar can be transformed into an equivalent one in a particular form, by paying a polynomial size increase.

Corollary 1. Each nse grammar is equivalent to a grammar in Chomsky normal form of polynomial size, in which, for each production X → Y Z, Y is greater than X according to the order induced by the production graph.

Proof. By Theorem 2, from each nse grammar G we can obtain an equivalent h-pda A of polynomial size which, according to Theorem 3, can be transformed into an equivalent nse grammar G as defined above. As observed in the proof of Lemma 4, if X + =⇒ αXβ in G , then β should be empty. This implies that for each production X → Y Z, Y is greater than X according to the order induced by the production graph. Furthermore, it is routine to prove that the unit productions can be eliminated yielding a grammar G of the desired form.

nse Grammars versus 1-las

In this section, we compare the sizes of nse grammars and of h-pdas with the size of equivalent limited automata. We prove that for each nse grammar there exists an equivalent 1-la of polynomial size. As a consequence, the simulation of constant height pdas by a 1-la is polynomial in size.

Concerning the converse transformation, we prove that 1-las can be more succinct than nse grammars and constant height pdas. Actually, we prove a stronger result showing the existence of a family (L n ) n>0 of languages such that each L n is accepted by a 2dfa with O(n) states, while each Chomsky normal form grammar or pda accepting L n would require an exponential size in n.

From nse grammars to 1-las

We start from an nse grammar G = V, Σ, P, S in the form given by Corollary 1. Thus, there exists a constant c ≤ #V , such that every derivation tree of G has the following properties:

-Each internal node is either saturated (i.e., it has exactly two children) and its children are labeled by some variables, or it has a unique child which is labeled by a terminal symbol.

-Along every path, the number of left turns (i.e., the number of nodes which are left-child of some node) is bounded by c.

These properties allow us to compress the representation of a derivation tree generating a word w of length m into a word u of length m over the alphabet Γ = Σ × V × {0, . . . , c}. The compression is non-injective, thus u may encode different derivation trees. However, each of these derivation trees should generate the same word w, which is the projection of u over Σ.

We now describe the compression, which is illustrated in Figure 2. Given a derivation tree T of G, we inductively index its internal nodes according to the following rules:

the root of T , labeled by the start symbol S, has index 0; the left-child of a node with index i, has index i + 1; the right-child of a node with index i, has index i.

In other words, the index of an internal node indicates the number of left turns along the path from the root to it. By assumption on G, this number is bounded by c.

S, 0 A, 1 C, 2 b (b, C, 2) B, 1 C, 2 b (b, C, 2) A, 1 a (a, A, 1) S, 0 B, 1 C, 2 b (b, C, 2) A, 1 a (a, B, 1) C, 0 b (b, S, 0) µ(T ) = w =

Fig. 2. An example of derivation tree

For a leaf of the tree labeled by a terminal symbol a ∈ Σ, we define σ = (a, X, i) ∈ Γ where (X, i) is the indexed label of the lowest ancestor of (namely, with minimal i) which is not a right-child of any node (such nodes have square shape in Figure 2). The compression of the derivation tree T is defined as the word µ(T ) = σ 1 • • • σ m where 1 , . . . , m are the leaves of T taken from left to right.

We now show how to check that a word u ∈ Γ + is the compression of some derivation tree. To this end, we highlight the recursive structure of compressions. We first define the three natural projections over Γ : for a symbol σ = (a, X, i) ∈ Γ , we set letter(σ) = a, var(σ) = X and index(σ) = i.

We fix the convention index( ) = index( ) = -1. For i = 0, . . . , c, we define Γ >i , the restriction of Γ to symbols of index greater than i, i.e.,

Γ >i = {σ ∈ Γ | index(σ) > i}.
of a symbol preceding a symbol of index i, is always less than or equal to i + 1. For instance, the compression illustrated in Figure 2 and (b, C, 2)(a, B, 1) which correspond to the subtree rooted in the squareshape nodes (A, 1) and (B, 1), respectively.

We now show how a 2nfa can check whether a word u ∈ Γ + is a valid compression. Basically, the device implements the above-given inductive definition of valid compressions, with the difference that it test each subtree of level from c downto 0 instead of performing recursive calls. This allows to store only one guessed variable Z at each time. We describe the behavior of such a 2nfa A through a collection of subroutines, the top-level of which is the procedure CheckTree. In each subroutine, σ denotes the symbol currently scanned by the head, which is automatically updated at each head move. To summarize, we obtained the following result. Lemma 6. The language of valid compressions is recognized by a 2nfa which uses O(#V 2 ) states.

Procedure CheckTree

Proof. The construction of such a 2nfa A has been described above. We now estimate its size. The only memory used in the procedure CheckTree, We are now ready to state our main result. Theorem 4. For every nse grammar G, there exist a 1-state letter-toletter nondeterministic transducer T and a 2nfa A of polynomial size, such that a word w is generated by G if and only if A accepts an image u of w by T . As a consequence, G can be transformed into an equivalent 1la of polynomial size.

Proof. From an nse grammar, we obtain an nse grammar G over Σ of polynomial size in the form given by Corollary 1. The transducer T replaces each letter a ∈ Σ by a symbol (a, X, i) for some variable X of G and some index i ≤ #V . Finally, we build A, using Lemma 6, which recognize an output of T , if and only if its pre-image were generated by G, by Lemma 5.

The following result directly follows from Theorems 3 and 4. We are now ready to prove the announced exponential gap. For a positive integer n, let L n be the language of the powers of any string of length n over {0, 1}, i.e., L n = u k | u ∈ {0, 1} n , k ≥ 0 .

Figure 1 Fig. 1 .

 11 Figure1summarizes the main results discussed in the paper.

4

  Draft: Wednesday 10 th May, 2023 14:05

Lemma 1 .

 1 by applying a standard transformation, it is possible to obtain an equivalent constant height pda. Unfortunately, the argument fails when the grammar contains left recursive derivations, i.e., derivations of the form A + =⇒ Aγ. For them, the resulting pda has computations with arbitrarily high pushdown stores. This problem can be fixed by replacing each left-linear grammar corresponding to a scc of the production graph of the given nse grammar by one equivalent right-linear grammar, as shown in the following lemma: Each nse grammar can be converted into an equivalent nse grammar of polynomial size which can be expressed as a composition of right-linear grammars.

8

  Draft: Wednesday 10 th May, 2023 14:05 Now suppose to have an nse grammar G, where G = G 1 ⊕G 2 ⊕• • •⊕G g and each G i is left-linear or right-linear. The idea is to define an equivalent grammar G by keeping each right-linear G i , and by replacing each left-linear G i by an equivalent right-linear grammar. However, when doing grammar composition, we could use derivations of G i that begin from variables of V i different than the start symbol S i . For this reason, we replace each left-linear G i by a family of right-linear grammars

  a terminal string. The derivation under consideration can be decomposed as A =⇒ lm y 1 A 1 =⇒ lm y 1 x 1 α, where A 1 ∈ V i . Now, we can repeat the previous proof on the subderivation A 1 =⇒ lm x 1 α, either reaching the previous case and, hence, proving that |α| ≤ K(g -i) + 1, or returning to this case with a further subderivation A 2 =⇒ lm x 2 α. This argument can be iterated. At each step, a subderivation of the derivation at the previous step is considered. So, in a finite number of steps we will reach the previous case obtaining the desired conclusion.From the grammar G we can apply a standard construction to obtain a pda M which simulates a leftmost derivation of G by replacing any variable A occurring on the top of the pushdown, by the right-hand side of a production A → α, and by popping off the pushdown any terminal symbol occurring on the top and matching the next input symbol (for details see, e.g.,[START_REF] Hopcroft | Introduction to automata theory, languages, and computation[END_REF]). After consuming an input prefix y, the pushdown store of M can contain any string zα such that S =⇒ lm yzα, yz is the longest prefix of yzα consisting only of terminal symbols, and z is a suitable factor of the string which was most recently pushed on the pushdown. Since |z| ≤ K and, according to the first part of the proof |α| ≤ K(g -1) + 1, we conclude that the pushdown height is bounded by Kg + 1. Hence, M is a constant height pda. Finally, M can be converted in the form given in Definition 2, by keeping its size polynomial. 10 Draft: Wednesday 10 th May, 2023 14:05

  ), (3), and, possibly, the further condition (2 ). If k = 1 then C should consist only of one move, which consumes the input symbol x = a and does not modify the pushdown store. According to the definition of G, the only possible derivations corresponding to such path are pAq =⇒ x and [pAq] =⇒ pAq =⇒ x.

  admits two valid compressions of level 1, namely the factors (b, C, 2)(b, C, 2)(a, A, 1)

/ 5 CheckSubtree(i) 6 move

 56 * start with the head on the left endmarker */ 1 CheckZeroes 2 for i ← c downto 0 do 3 move the head to the right until reaching the next symbol with index i 4 while index(σ) = i do the head to the right until reaching the next symbol with index i 7 move the head to the left until reaching the left endmarker 8 AcceptAs initial phase, the subroutine CheckZeroes checks that the input word belongs to Γ * >0 • (a, S, 0) for some letter a ∈ Σ. Then, A checks the validity of each compressions of each level from c downto 0 (for loop from line 2 to 7). This verification uses the procedure CheckSubtree (call line 5). 20 Draft: Wednesday 10 th May, 2023 14:05 Procedure CheckZeroes 9 move the head to the right until reaching the right endmarker 10 move the head to the left 11 if var(σ) = S or index(σ) = 0 then Reject 12 while σ = do 13 move the head to the left 14 if index(σ) = 0 then Reject This latter subroutine is the direct implementation of the inductive definition of valid compressions, where the recursive call to incremented level (Item 2c) are omitted (the validity of these sub-compressions have already been checked by previous call to the procedure CheckSubtree). It uses the subroutine SelectNext which finds the leftmost symbol of index i + 1 in the factor under consideration, if any, or checks whether the factor has length 1 (if not, the computation rejects, line 19), thus checking Item 2b (or, partially, Item 1). Items 1 and 2a correspond to Procedure SelectNext(i) 15 move the head to the right 16 if index(σ) = i -1 then return 17 else 18 while index(σ) > i do move the head to the right 19 if index(σ) = i then Reject lines 28 and 25, respectively, while C contains the variable Z (line 26) which is initially set to X (line 20), thus allowing to verify Item 2d (while loop lines 23 to 27).

21

  Draft: Wednesday 10 th May, 2023 14:05 Procedure CheckSubtree(i) /* start with the head scanning a symbol of index i */ 20 C ← var(σ) 21 repeat move the head to the left until index(σ) ≤ i 22 SelectNext(i + 1) 23 while index(σ) = i do 24 guess Z 25 if C → Y Z ∈ P , where Y = var(σ) then Reject 26 C ← Z 27 SelectNext(i + 1) 28 if C → a ∈ P , where a = letter(σ) then Reject is an index i ∈ {0, . . . , c}, to which both the subroutines SelectNext and CheckSubtree have read-only access. The subroutines CheckZeroes and SelectNext use no additional memory. The procedure CheckSubtree stores one variable, namely C, which ranges over V . Hence, the number of states of A is linear in c × #V . Since c ≤ #V , the number of states of A is in O(#V 2 ).

Corollary 2 .

 2 Each h-pda can be transformed into an equivalent 1-la of polynomial size.

4. 2 Lemma 7 .

 27 From 2dfas to pdas: An Exponential GapIn this section, we exhibit an infinite family (L n ) n≥0 of languages over the alphabet {0, 1}, such that each L n is recognized by a 1-la with linear size in n, but requires an exponential size in order to be recognized by an h-pda. We actually prove a stronger result, since each L n is recognized by a 2dfa of linear size, while any grammar in Chomsky normal form generating L n requires an exponential number of variables. As a consequence, every pda recognizing L n requires an exponential size.The proof of this lower bound is obtained by using the interchange lemma [15, Lemma 4.5.1]: Given a context-free language L, there exists a constant c > 0, such that for every integer N ≥ 2, every subset R ⊆ L ∩ Σ N of strings of length N , and every integer m with 2 ≤ m ≤ N , there exists a sub-set Z ⊆ R with Z = {z 1 , z 2 , . . . , z k } such that k ≥ #R c(N +1) 2, and there exist decompositions z i = w i x i y i , with 1 ≤ i ≤ k, such that the following conditions are satisfied:1. |w 1 | = |w 2 | = • • • = |w k |; 2. |y 1 | = |y 2 | = • • • = |y k |; 3. m 2 < |x 1 | = |x 2 | = • • • = |x k | ≤ m; 4. w i x j y i ∈ L for all i, j with 1 ≤ i, j ≤ k.Furthermore, c can be taken as the number of variables of any context-free grammar in Chomsky normal form generating L.

Theorem 5 .

 5 For each n > 0, the following holds:-L n isaccepted by a 2dfa of size O(n); 23 Draft: Wednesday 10 th May, 2023 14:05

Draft: Wednesday 10 th May, 2023 14:05

Draft: Wednesday 10 th May, 2023 14:05

was accepted by the original h-pda A. Acceptance is furthermore done by empty pushdown, indeed the only final state (q + , 0) stores the information that the current pushdown height is 0. Moreover, the projection h over the pushdown alphabet Γ , associates to each pushdown symbol, the only height index to which it may appear in the pushdown store.

Let A = Q, Σ, Γ, δ, q -, {q + }, h be an h-pda in the form of Lemma 2.

In particular, A does not accept the empty word. We define a grammar G = V, Σ, P, S , where V consists of an initial symbol S and of triples of the form [qAp] and qAp , for q, p ∈ Q, A ∈ Γ . The set P consists of the following productions:

for (p, +X, p ), (q , -X, q) ∈ δ, i.e., push and pop of a same symbol X

where ⊥ / ∈ Γ is a new symbol denoting the "missed top" in the empty pushdown store.

The above definition is derived from the classical construction of cfgs from pdas, introducing two types of triples in order to obtain an nse grammar. (A simpler construction, as that in [START_REF] Pighizzini | Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds[END_REF], would produce a selfembedding grammar.) More precisely, we can prove the following:

there exists a computation path C of A verifying the following conditions:

(1) C starts in the state p and ends in the state q, in both these configurations the symbol at the top of the pushdown is A;

(2) along C the pushdown is never popped off under its level at the beginning of C;

(3) the input factor consumed along C is x.

A word u ∈ Γ + is a valid compression of level i, 0 ≤ i ≤ c, if, on the one hand, u = w • (a, X, i) for some w ∈ Γ * >i , a ∈ Σ and X ∈ V , and, on the other hand, one of the following two cases holds:

1. w = ε and X → a belongs to P ;

In particular, valid compressions of level c are exactly the single-letter word (a, X, c) such that X → a ∈ P . Observe that in Case 2, Item 2c implies v ∈ Γ * >i+1 and therefore, Y and b are read from the leftmost symbol of index i + 1 of u. Hence, in order to reconstruct the tree, only the variables "Z's" should be guessed (these variables correspond indeed to nodes that are right-child of some node, represented with circle shape on Figure 2, which are therefore not represented in the compression of the tree). By construction, we have: Lemma 5. A word u ∈ Γ + is a valid compression of level 0 if and only if u = µ(T ) for some derivation tree T of G. Furthermore, T generates a word w ∈ Σ + which equals the projection of u over Σ * .

Proof. We simply observe that Items 1 and 2a check that the recovered tree is consistent with the productions of G, and that Items 2c and 2d are recursive calls on the left and right subtrees, respectively. Conversely, a correct derivation tree can be recovered from its (valid) compression.

In every compression µ(T ) of some derivation tree T , and for every level index i, a valid compression of level i is a factor delimited to the left, by a symbol of index less than i (not included in the factor), and to the right, by the symbol of index i corresponding to its root node (included in the factor). This allows a reading head to locally detect the boundaries of such a factor of an input. This also implies, that the index nentially many variables in n to generate L n ; -The size of any pda accepting L n is at least exponential in n.

Proof. A 2dfa A with O(n) states can accept L n as follows. First A traverses the whole input tape, in order to verify that the input length is a multiple of n. Then A, by moving the head back and forth, verifies that all two symbols at distance n are equal. It is not difficult to observe that A can be implemented using O(n) states.

To prove that each context-free grammar generating L n requires an exponential number of variables, we observe that given u, u ∈ {0, 1} n , if we decompose the strings z = uuu and z = u u u ∈ L n as z = Proof. The lower bound derives from Theorem 5. For the upper bound, in [START_REF] Pighizzini | Limited automata and regular languages[END_REF] it was proved that each 1-la can be transformed into an nfa of exponential size from which, by a standard construction, we can obtain a regular (and, so, nse) grammar, without increasing the size.

In [START_REF] Bednárová | Removing nondeterminism in constant height pushdown automata[END_REF], the question of the cost of the conversion of deterministic h-pdas into nfas was raised. To this regard, we observe that the language (a 2 n ) * 24 Draft: Wednesday 10 th May, 2023 14:05 is accepted by a deterministic h-pda (see, e.g., [START_REF] Pighizzini | Deterministic pushdown automata and unary languages[END_REF]) but, by a standard pumping argument, it requires at least 2 n states to be accepted by nfas.

Actually, as a consequence of state lower bound presented in [9, Theorem 9], 2 n states are also necessary to accept it on each 2nfa. Considering Theorem 5, we can conclude that both simulations from two-way automata to h-pdas and from h-pdas to two-way automata cost at least exponential.


Modélisation individuelle de juges pour la prédiction automatique de l'intelligibilité de la parole

Sebastião QUINTAS Julie MAUCLAIR Julien PINQUIER IRIT, Université de Toulouse, CNRS, Toulouse INP, UT3, Toulouse, France

Le développement d'outils automatiques pour la prédiction de l'intelligibilité de la parole peut être vu comme une alternative plus robuste, reproductible et objective face aux évaluations perceptives réalisées en clinique. En effet, ces évaluations peuvent être conditionnées par une variété d'aspects, tels que la connaissance préalable du patient ou la tâche d'évaluation de la parole elle-même (Balaguer et al., 2019). Les travaux de (De Bodt et al., 2002) ont montré que l'intelligibilité de la parole est liée à quatre paramètres perceptifs : Voix (V), Résonance (R), Prosodie (P) et Distorsions Phonémiques (PD), mais avec des niveaux de pertinence variables en fonction de chaque juge. Vu que l'intelligibilité est une mesure intrinsèquement subjective, la modélisation des juges individuels devient pertinente dans le contexte de l'intelligibilité de la parole (Woisard et al., 2021).

Dans cette étude, nous faisons la modélisation d'un ensemble de juges perceptifs, utilisés pour la prédiction de l'intelligibilité dans la cadre du corpus français du cancer des voies aérodigestives supérieures (Woisard et al., 2020). Nous nous basons sur le paradigme des X-vector speaker embeddings (Quintas et al., 2020) afin de proposer la modélisation illustrée sur la figure 1. Chaque modèle individuel reçoit en entrée une représentation, qui est ensuite transmise à un réseau neuronal peu profond. Ce réseau prédit les quatre paramètres perceptifs : Voix (V), Résonance (R), Prosodie (P) et Distorsions Phonémiques (PD). Ensuite, l'intelligibilité est prédite en fonction de ces quatre paramètres, en utilisant une moyenne simple (poids uniformes) ou pondérée, qui utilise des poids différents pour chaque paramètre. Pour chercher les poids optimaux pour la moyenne pondérée, une méthode par grille de recherche (grid search) a été conçue.

Dans le tableau 1, nous pouvons observer deux analyses distinctes. La première montre la prédiction d'intelligibilité en utilisant les quatre paramètres perceptifs de chaque juge. La seconde montre exactement la même prédiction avec la modélisation automatique présentée précédemment. Malgré les corrélations inférieures dans la modélisation automatique de chaque juge, la différence entre les résultats obtenus avec les poids uniformes et les poids grid search est plus faible que dans le cas de l'analyse perceptive. Puisqu'il existe différents profils parmi les différents juges perceptifs (De Bodt et al., 2002), nous pouvons dire que la modélisation automatique favorise une prédiction, non seulement plus homogène entre les différents paramètres utilisés, mais également plus explicable. L'explicabilité des systèmes automatiques et des mesures produites devrait permettre une meilleure acceptabilité par les cliniciens.

Figure 1 .

 1 Figure 1. Schéma de la modélisation individuelle de chaque juge perceptif.

  Tableau 1. Corrélations obtenues en utilisant des moyennes des 4 paramètres perceptifs.Comparaison entre l'analyse perceptive et la modélisation automatique des juges.Balaguer, M., Pommée, T., Farinas J., Pinquier, J., Woisard V., & Speyer, R. (2019). Effects of oral and oropharyngeal cancer on speech intelligibility using acoustic analysis: Systematic review. Journal of the Sciences and Specialities of Head and Neck.Woisard, V., Balaguer, M.,Fredouille, C., & al. (2021). Construction of an automatic score for the evaluation of speech disorders among patients treated for a cancer of the oral cavity or the oropharynx: The Carcinologic Speech Severity Index, Head & Neck.Woisard,V., & al. (2020). C2SI corpus: a database of speech disorder productions to assess intelligibility and quality of life in head and neck cancers, Language Resources Evaluation.

		Analyse perceptive des juges	Modélisation automatique des juges
	Juge	Poids Uniformes	Poids Grid Search	Poids Uniformes	Poids Grid Search
	1	0,828	0,851	0,613	0,630
	2	0,774	0,852	0,699	0,728
	3	0,836	0,879	0,613	0,633
	4	0,767	0,863	0,726	0,742
	5	0,648	0,784	0,490	0,539
	6	0,750	0,810	0,637	0,649
		Références bibliographiques
	Quintas, S., Mauclair, J., Woisard, V., & Pinquier, J. (2020). Automatic Prediction of
	Speech Intelligibility Based on X-Vectors in the Context of Head and Neck Cancer,
	Proceedings of Interspeech.
	De Bodt, M. S., Hérnandez-Diaz Huici, M. E., & Van De Heyning, P. H (2002).
	Intelligibility as a Linear Combination of Dimensions in Dysarthric Speech. Journal
	of Communication Disorders.