# Strictly Locally Testable and Resources Restricted Control Languages in
Tree-Controlled Grammars

Bianca Truthe Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392
Giessen, Germany<EMAIL_ADDRESS>
###### Abstract

Tree-controlled grammars are context-free grammars where the derivation
process is controlled in such a way that every word on a level of the
derivation tree must belong to a certain control language. We investigate the
generative capacity of such tree-controlled grammars where the control
languages are special regular sets, especially strictly locally testable
languages or languages restricted by resources of the generation (number of
non-terminal symbols or production rules) or acceptance (number of states).
Furthermore, the set theoretic inclusion relations of these subregular
language families themselves are studied.

##  1 Introduction

In the monograph [6] by Jürgen Dassow and Gheorghe Păun, _Seven Circumstances
Where Context-Free Grammars Are Not Enough_ are presented. A possibility to
enlarge the generative power of context-free grammars is to introduce some
regulation mechanism which controls the derivation in a context-free grammar.
In some cases, regular languages are used for such a regulation. They are
rather easy to handle and, used as control, they often lead to context-
sensitive or even recursively enumerable languages while the core grammar is
only context-free.

One such control mechanism was introduced by Karel Čulik II and Hermann A.
Maurer in [17] where the structure of derivation trees of context-free
grammars is restricted by the requirement that the words of all levels of the
derivation tree must belong to a given regular (control) language. This model
is called tree-controlled grammar.

Gheorghe Păun proved that the generative capacity of such grammars coincides
with that of context-sensitive grammars (if no erasing rules are used) or
arbitrary phrase structure grammars (if erasing rules are used). Thus, the
question arose to what extend the restrictions can be weakened in order to
obtain ‘useful’ families of languages which are located somewhere between the
classes of context-free and context-sensitive languages.

In [7, 8, 9, 10, 28, 30, 31], many subregular families of languages have been
investigated as classes for the control languages. In this paper, we continue
this research with further subregular language families, especially strictly
locally testable languages or languages restricted by resources of the
generation (number of non-terminal symbols or production rules) or acceptance
(number of states). Furthermore, the set theoretic inclusion relations of
these subregular language families themselves are studied.

##  2 Preliminaries

Throughout the paper, we assume that the reader is familiar with the basic
concepts of the theory of automata and formal languages. For details, we refer
to [24]. Here we only recall some notation and the definition of contextual
grammars with selection which form the central notion of the paper.

###  2.1 Languages, grammars, automata

Given an alphabet $V$, we denote by $V^{*}$ and $V^{+}$ the set of all words
and the set of all non-empty words over $V$, respectively. The empty word is
denoted by $\lambda$. By $V^{k}$, and $V^{{}\leq k}$ for some natural number
$k$, we denote the set of all words of the alphabet $V$ with exactly $k$
letters and the set of all words over $V$ with at most $k$ letters,
respectively. For a word $w$ and a letter $a$, we denote the length of $w$ by
$|w|$ and the number of occurrences of the letter $a$ in the word $w$ by
$|w|_{a}$. For a set $A$, we denote its cardinality by $|A|$.

A right-linear grammar is a quadruple $G=(N,T,P,S)$ where $N$ is a finite set
of non-terminal symbols, $T$ is a finite set of terminal symbols, $P$ is a
finite set of production rules of the form $A\rightarrow wB$ or $A\rightarrow
w$ with $A,B\in N$ and $w\in T^{*}$, and $S\in N$ is the start symbol. Such a
grammar is called regular, if all the rules are of the form $A\rightarrow xB$
or $A\rightarrow x$ with $A,B\in N$ and $x\in T$ or $S\rightarrow\lambda$. The
language generated by a right-linear or regular grammar is the set of all
words over the terminal alphabet which are obtained from the start symbol $S$
by a successive replacement of the non-terminal symbols according to the rules
in the set $P$. A non-terminal symbol $A$ is replaced by the right-hand side
$w$ of a rule $A\rightarrow w\in P$ in order to derive the next sentential
form. The language generated consists of all sentential forms without a non-
terminal symbol. Every language generated by a right-linear grammar can also
be generated by a regular grammar.

A deterministic finite automaton is a quintuple $A=(V,Z,z_{0},F,\delta)$ where
$V$ is a finite set of input symbols, $Z$ is a finite set of states, $z_{0}\in
Z$ is the initial state, $F\subseteq Z$ is a set of accepting states, and
$\delta$ is a transition function $\delta:Z\times V\to Z$. The language
accepted by such an automaton is the set of all input words over the alphabet
$V$ which lead letterwise by the transition function from the initial state to
an accepting state.

A regular expression over an alphabet $V$ is defined inductively as follows:

  1. 1.

$\emptyset$ is a regular expression;

  2. 2.

every element $x\in V$ is a regular expression;

  3. 3.

if $R$ and $S$ are regular expressions, so are the concatenation $R\cdot S$,
the union $R\cup S$, and the Kleene closure $R^{*}$;

  4. 4.

for every regular expression, there is a natural number $n$ such that the
regular expression is obtained from the atomic elements $\emptyset$ and $x\in
V$ by $n$ operations concatenation, union, or star.

The language $L(R)$ which is described by a regular expression $R$ is also
inductively defined: $L(\emptyset)=\emptyset$; $L(x)=\\{x\\}$ for each $x\in
V$; and $L(R\cdot S)=L(R)\cdot L(S)$, $L(R\cup S)=L(R)\cup L(S)$, and
$L(R^{*})=(L(R))^{*}$ for regular expressions $R$ and $S$.

The set of all languages generated by some right-linear grammar coincides with
the set of all languages accepted by a deterministic finite automaton and with
the set of all languages described by a regular expression. All these
languages are called regular and form a family denoted by $\mathit{REG}$. Any
subfamily of this set is called a subregular language family.

A context-free grammar is a quadruple $G=(N,T,P,S)$ where $N$, $T$, and $S$
are as in a right-linear grammar but the production rules in the set $P$ are
of the form $A\rightarrow w$ with $A\in N$ and $w\in(N\cup T)^{*}$.

The language generated by a context-free grammar is the set of all words over
the terminal alphabet which are obtained from the start symbol $S$ by
replacing sequentially the non-terminal symbols according to the rules in the
set $P$. A language is called context-free if it is generated by some context-
free grammar. The family of all context-free languages is denoted by
$\mathit{CF}$.

With a derivation of a terminal word by a context-free grammar, we associate a
derivation tree which has the start symbol in its root and where every node
with a non-terminal $A\in N$ has as children nodes with symbols which form,
read from left to right, a word $w$ such that $A\rightarrow w$ is a rule of
the grammar (if $A\rightarrow\lambda$, then the node with $A$ has only one
child node and this is labelled with $\lambda$). Nodes with terminal symbols
or $\lambda$ have no children. With any derivation tree $t$ of height $k$ and
any number $0\leq j\leq k$, we associate the word of level $j$ and the
sentential form of level $j$ which are given by all nodes of depth $j$ read
from left to right and all nodes of depth $j$ and all leaves of depth less
than $j$ read from left to right, respectively. Obviously, if two words $w$
and $v$ are sentential forms of two successive levels, then
$w\Longrightarrow^{*}v$ holds and this derivation is obtained by a parallel
replacement of all non-terminal symbols occurring in the word $w$.

A context-sensitive grammar is a quadruple $G=(N,T,P,S)$ where $N$ is a finite
set of non-terminal symbols, $S\in N$ is the start symbol, $T$ is a finite set
of terminal symbols, and $P$ is a finite set of production rules of the form
$\alpha\rightarrow\beta$ with $\alpha\in(N\cup T)^{+}\setminus T^{*}$,
$\beta\in(N\cup T)^{*}$, and $|\beta|\geq|\alpha|$ with the only exception
that $S\rightarrow\lambda$ is allowed if the sysmbol $S$ does not occur on any
right-hand side of a rule. The language generated by a context-sensitive
grammar is the set of all words over the terminal alphabet which are obtained
from the start symbol $S$ by replacing sequentially subwords according to the
rules in the set $P$. A language is called context-sensitive if it is
generated by some context-sensitive grammar. The family of all context-
sensitive languages is denoted by $\mathit{CS}$. For every context-sensitive
language $L$, there is a context-sensitive grammar $G=(N,T,P,S)$ with
$L(G)=L$, where all rules in $P$ are of the form

$AB\rightarrow CD,\ A\rightarrow BC,\ A\rightarrow B,\mbox{ or }A\rightarrow
a$

with $A,B,C,D\in N$ and $a\in T$, or $S\rightarrow\lambda$ if $S$ does not
occur on the right-hand side of a rule. Such a grammar is said to be in Kuroda
normal form ([18]).

We also mention here four classes of languages without a definition since they
are mentioned only in the summary of existing results: By $\mathit{MAT}$, we
denote the family of all languages generated by matrix grammars with
appearance checking and without erasing rules; by
$\mathit{MAT}_{\mathit{fin}}$, we denote the family of all such languages
where the matrix grammar is of finite index ([6], [24]). By $\mathit{E0L}$
($\mathit{ET0L}$), we denote the family of all languages generated by extended
(tabled) interactionless Lindenmayer systems ([23]).

###  2.2 Complexity measures and resources restricted languages

Let $G=(N,T,P,S)$ be a right-linear grammar, $A=(V,Z,z_{0},F,\delta)$ be a
deterministic finite automaton, and $L$ be a regular language. Then, we recall
the following complexity measures from [5]:

$\displaystyle\mathit{State}(A)$
$\displaystyle=|Z|,\mathit{Var}(G)=|N|,\mathit{Prod}(G)=|P|,$
$\displaystyle\mathit{State}(L)$
$\displaystyle=\min\left\\{\>\mathit{State}(A)\;|\;A\mbox{ is a det. finite
automaton accepting }L\>\right\\},$
$\displaystyle\mathit{Var}_{\mathit{RL}}(L)$
$\displaystyle=\min\left\\{\>\mathit{Var}(G)\;|\;G\mbox{ is a right-linear
grammar generating }L\>\right\\},$
$\displaystyle\mathit{Prod}_{\mathit{RL}}(L)$
$\displaystyle=\min\left\\{\>\mathit{Prod}(G)\;|\;G\mbox{ is a right-linear
grammar generating }L\>\right\\}.$

We now define subregular families by restricting the resources needed for
generating or accepting their elements:

$\displaystyle\mathit{RL}_{n}^{V}$
$\displaystyle=\left\\{\>L\;|\;L\in\mathit{REG}\mbox{ with
}\mathit{Var}_{\mathit{RL}}(L)\leq n\>\right\\},$
$\displaystyle\mathit{RL}_{n}^{P}$
$\displaystyle=\left\\{\>L\;|\;L\in\mathit{REG}\mbox{ with
}\mathit{Prod}_{\mathit{RL}}(L)\leq n\>\right\\},$
$\displaystyle\mathit{REG}_{n}^{Z}$
$\displaystyle=\left\\{\>L\;|\;L\in\mathit{REG}\mbox{ with
}\mathit{State}(L)\leq n\>\right\\}.$

###  2.3 Subregular language families based on the structure

We consider the following restrictions for regular languages. Let $L$ be a
language over an alphabet $V$. With respect to the alphabet $V$, the language
$L$ is said to be

  * •

_monoidal_ if and only if $L=V^{*}$,

  * •

_nilpotent_ if and only if it is finite or its complement $V^{*}\setminus L$
is finite,

  * •

_combinational_ if and only if it has the form $L=V^{*}X$ for some subset
$X\subseteq V$,

  * •

_definite_ if and only if it can be represented in the form $L=A\cup V^{*}B$
where $A$ and $B$ are finite subsets of $V^{*}$,

  * •

_suffix-closed_ (or _fully initial_ or _multiple-entry_ language) if and only
if, for any two words $x\in V^{*}$ and $y\in V^{*}$, the relation $xy\in L$
implies the relation $y\in L$,

  * •

_ordered_ if and only if the language is accepted by some deterministic finite
automaton

$A=(V,Z,z_{0},F,\delta)$

with an input alphabet $V$, a finite set $Z$ of states, a start state
$z_{0}\in Z$, a set $F\subseteq Z$ of accepting states and a transition
mapping $\delta$ where $(Z,\preceq)$ is a totally ordered set and, for any
input symbol $a\in V$, the relation $z\preceq z^{\prime}$ implies
$\delta(z,a)\preceq\delta(z^{\prime},a)$,

  * •

_commutative_ if and only if it contains with each word also all permutations
of this word,

  * •

_circular_ if and only if it contains with each word also all circular shifts
of this word,

  * •

_non-counting_ (or _star-free_) if and only if there is a natural number
$k\geq 1$ such that, for every three words $x\in V^{*}$, $y\in V^{*}$, and
$z\in V^{*}$, it holds $xy^{k}z\in L$ if and only if $xy^{k+1}z\in L$,

  * •

_power-separating_ if and only if, there is a natural number $m\geq 1$ such
that for every word $x\in V^{*}$, either $J_{x}^{m}\cap L=\emptyset$ or
$J_{x}^{m}\subseteq L$ where $J_{x}^{m}=\\{\;x^{n}\mid n\geq m\;\\}$,

  * •

_union-free_ if and only if $L$ can be described by a regular expression which
is only built by product and star,

  * •

_strictly locally $k$-testable_ if and only if there are three subsets $B$,
$I$, and $E$ of $V^{k}$ such that any word $a_{1}a_{2}\ldots a_{n}$ with
$n\geq k$ and $a_{i}\in V$ for $1\leq i\leq n$ belongs to the language $L$ if
and only if

$\displaystyle a_{1}a_{2}\ldots a_{k}\in B,$ $\displaystyle
a_{j+1}a_{j+2}\ldots a_{j+k}\in I\text{ for every $j$ with $1\leq j\leq n-k-1$
and}$ $\displaystyle a_{n-k+1}a_{n-k+2}\ldots a_{n}\in E,$

  * •

_strictly locally testable_ if and only if it is strictly locally $k$-testable
for some natural number $k$.

We remark that monoidal, nilpotent, combinational, definite, ordered, union-
free, and strictly locally ($k$-)testable languages are regular, whereas non-
regular languages of the other types mentioned above exist. Here, we consider
among the commutative, circular, suffix-closed, non-counting, and power-
separating languages only those which are also regular.

Some properties of the languages of the classes mentioned above can be found
in [25] (monoids), [12] (nilpotent languages), [14] (combinational and
commutative languages), [20] (definite languages), [13] and [3] (suffix-closed
languages), [26] (ordered languages), [4] (circular languages), [19] (non-
counting and strictly locally testable languages), [27] (power-separating
languages), [2] (union-free languages).

By $\mathit{FIN}$, $\mathit{MON}$, $\mathit{NIL}$, $\mathit{COMB}$,
$\mathit{DEF}$, $\mathit{SUF}$, $\mathit{ORD}$, $\mathit{COMM}$,
$\mathit{CIRC}$, $\mathit{NC}$, $\mathit{PS}$, $\mathit{UF}$,
$\mathit{SLT}_{k}$ (for any natural number $k\geq 1$), and $\mathit{SLT}$, we
denote the families of all finite, monoidal, nilpotent, combinational,
definite, regular suffix-closed, ordered, regular commutative, regular
circular, regular non-counting, regular power-separating, union-free, strictly
locally $k$-testable, and strictly locally testable languages, respectively.

For any natural number $n\geq 1$, let $\mathit{MON}_{n}$ be the set of all
languages that can be represented in the form $A_{1}^{*}\cup
A_{2}^{*}\cup\cdots\cup A_{k}^{*}$ with $1\leq k\leq n$ where all $A_{i}$
($1\leq i\leq k$) are alphabets. Obviously,

$\mathit{MON}=\mathit{MON}_{1}\subset\mathit{MON}_{2}\subset\dots\subset\mathit{MON}_{j}\subset\cdots.$

A strictly locally testable language characterized by three finite sets $B$,
$I$, and $E$ as above which includes additionally a finite set $F$ of words
which are shorter than those of the sets $B$, $I$, and $E$ is denoted by
$\textbf{\rm[}B,I,E,F\textbf{\rm]}$.

As the set of all families under consideration, we set

$\displaystyle\mathfrak{F}$
$\displaystyle=\\{\mathit{FIN},\mathit{NIL},\mathit{COMB},\mathit{DEF},\mathit{SUF},\mathit{ORD},\mathit{COMM},\mathit{CIRC},\mathit{NC},\mathit{PS},\mathit{UF}\\}$
$\displaystyle\quad{}\cup\\{\;\mathit{MON}_{k}\mid k\geq
1\;\\}\cup\\{\mathit{SLT}\\}\cup\\{\;\mathit{SLT}_{k}\mid k\geq 1\;\\}$
$\displaystyle\quad{}\cup\\{\;\mathit{RL}_{n}^{V}\mid n\geq
1\;\\}\cup\\{\;\mathit{RL}_{n}^{P}\mid n\geq
1\;\\}\cup\\{\;\mathit{REG}_{n}^{Z}\mid n\geq 1\;\\}.$

###  2.4 Hierarchy of subregular families of languages

In this section, we present a hierarchy of the families of the aforementioned
set $\mathfrak{F}$ with respect to the set theoretic inclusion relation. A
summary is depicted in Figure 1.

Before this, we prove some relations of the classes of strictly locally
$k$-testable languages to the subregular language families restricted by
resources, which have not been considered in the literature yet.

For this purpose, we first introduce some languages which serve later as
witness languages for proper inclusions and incomparabilities.

###### Lemma 2.1

The language $L_{1}=\\{a\\}^{*}\\{b\\}\\{a,b\\}^{*}$ belongs to
$\mathit{REG}_{2}^{Z}\setminus\mathit{SLT}$.

######  Proof 2.2.

The language $L_{1}$ is accepted by the automaton with two states whose
transition function is given in the following diagram (double-circled states
are accepting):

$z_{0}$start$z_{1}$$b$$a$$a,b$

Suppose, the language $L_{1}$ is strictly locally $k$-testable for some
natural number $k\geq 1$. Then, there exist sets $B\subseteq V^{k}$,
$I\subseteq V^{k}$, $E\subseteq V^{k}$, and $F\subseteq V^{{}\leq k-1}$ such
that $L_{1}=\textbf{\rm[}B,I,E,F\textbf{\rm]}$. Since the word $a^{2k}ba^{2k}$
belongs to the language $L_{1}$, we know that $a^{k}\in B\cap I\cap E$. But
then, also the word $a^{2k}$ belongs to the language which is a contradiction.

######  Lemma 2.3.

The language
$L_{2}=\textbf{\rm[}\\{a,b\\},\\{b,c\\},\\{a,c\\},\emptyset\textbf{\rm]}$
belongs to $\mathit{SLT}_{1}\setminus\mathit{REG}_{4}^{Z}$.

######  Proof 2.4.

By definition, $L_{2}\in\mathit{SLT}_{1}$.

We now prove that $L_{2}$ is not accepted by an deterministic finite automaton
with less than five states. Let $L=L_{2}$ and let $R_{L}$ be the Myhill-Nerode
equivalence relation (see [16]): two words $x$ and $y$ are in this relation if
and only if, for all words $z$, either both words $xz$ and $yz$ belong to the
language $L$ or none of them. The words $\lambda$, $a$, $b$, $c$, and $aa$ are
pairwise not in this relation, as one can check.

Therefore, the index of the language $L$ is at least five. Hence, at least
five states are necessary for accepting the language $L$.

######  Lemma 2.5.

For each natural number $n\geq 2$, let
$V_{n}=\\{a_{1},a_{2},\ldots,a_{n-1}\\}$ be an alphabet with $n-1$ pairwise
different letters and let $L_{3,n}=\\{a_{1}a_{2}\ldots a_{n-1}\\}$. Then,
every language $L_{3,n}$ for $n\geq 2$ belongs to the set
$\mathit{SLT}_{2}\setminus\mathit{REG}_{n}^{Z}$.

######  Proof 2.6.

The statement $L_{3,n}\in\mathit{SLT}_{2}$ for $n\geq 2$ can be seen as
follows. If $n=2$, then
$L_{3,n}=\textbf{\rm[}\emptyset,\emptyset,\emptyset,\\{a_{1}\\}\textbf{\rm]}$,
otherwise $L_{3,n}=\textbf{\rm[}\\{a_{1}a_{2}\\},\\{\;a_{p}a_{p+1}\mid 2\leq
p\leq n-3\;\\},\\{a_{n-2}a_{n-1}\\},\emptyset\textbf{\rm]}$.

For accepting any language $L_{3,n}$ for $n\geq 2$, at least $n+1$ states are
necessary (follows from the fact that the $n$ partial words $a_{1}\ldots
a_{i}$ for $0\leq i\leq n-1$ and $a_{1}a_{1}$ are pairwise not in the Myhill-
Nerode relation).

######  Lemma 2.7.

For each natural number $n\geq 1$, let $L_{4,n}=\\{a^{n}\\}$. Then $L_{4,n}$
belongs to the set $\mathit{RL}_{1}^{P}\setminus\mathit{SLT}_{n}$.

######  Proof 2.8.

The single word $a^{n}$ can be generated with one rule, hence,
$L_{4,n}\in\mathit{RL}_{1}^{P}$.

Assume that such a language is strictly locally $n$-testable. Then, it is
$L_{4,n}=\textbf{\rm[}B,I,E,F\textbf{\rm]}$ for suitable sets $B$, $I$, $E$,
and $F$. From $L_{4,n}=\\{a^{n}\\}$, it follows that $B=E=\\{a^{n}\\}$. But
then, also the word $a^{n+1}$ belongs to the language $L_{4,n}$ which is a
contradiction.

######  Lemma 2.9.

For each natural number $n\geq 1$, let $V_{n}=\\{a_{1},a_{2},\ldots,a_{n}\\}$
be an alphabet with $n$ pairwise different letters and let
$L_{5,n}=V_{n}^{*}$. Then, for $n\geq 1$, the language $L_{n}$ belongs to the
set $\mathit{SLT}_{1}\setminus\mathit{RL}_{n}^{P}$.

######  Proof 2.10.

The language $L_{5,n}$ can be represented as
$L_{5,n}=\textbf{\rm[}V,V,V,\\{\lambda\\}\textbf{\rm]}$. Hence,
$L_{5,n}\in\mathit{SLT}_{1}$ for $n\geq 1$.

For generating a language $L_{5,n}$ for some number $n\geq 1$, at least a non-
terminating rule is necessary for every letter $a_{i}$ ($1\leq i\leq n$) and
additionally a terminating rule. Hence, $L_{5,n}\notin\mathit{RL}_{n}^{P}$.

######  Lemma 2.11.

The language $L_{6}=\\{a\\}$ belongs to
$\mathit{RL}_{1}^{V}\setminus\mathit{SLT}_{1}$.

######  Proof 2.12.

The language $L_{6}$ can be generated with a single rule and, hence, with one
non-terminal only.

Assume that $L_{6}$ is strictly locally 1-testable and can be represented as
$\textbf{\rm[}B,I,E,F\textbf{\rm]}$. Then $B=E=\\{a\\}$. But then, also the
word $aa$ belongs to the language which is a contradiction.

######  Lemma 2.13.

The language $L_{7}=\\{a\\}\\{b\\}^{*}\\{a\\}\cup\\{a\\}$ belongs to
$\mathit{SLT}_{1}\setminus\mathit{RL}_{1}^{V}$.

######  Proof 2.14.

The language $L_{7}$ is strictly locally 1-testable and can be represented as
$\textbf{\rm[}\\{a\\},\\{b\\},\\{a\\},\emptyset\textbf{\rm]}$.

Assume that the language $L_{7}$ is generated by a right-linear grammar with
one non-terminal symbol only. Let $m$ be the maximal length of the right-hand
side of a rule: $m=\max(\\{\;w\mid S\rightarrow w\in P\;\\})$. Then, the word
$ab^{m}a$ cannot be derived in one step. Hence, there is a derivation
$S\Longrightarrow ab^{p}S\Longrightarrow^{*}ab^{m}a$ for some number $p$ with
$0\leq p\leq m-2$. But then, also the derivation $S\Longrightarrow
ab^{p}S\Longrightarrow ab^{p}ab^{p}S\Longrightarrow^{*}ab^{p}ab^{m}a$ is
possible which yields a word which does not belong to the language $L_{7}$.
Due to this contradiction, we obtain that $L_{7}\notin\mathit{RL}_{1}^{V}$.

######  Lemma 2.15.

The language $L_{8}=\\{\;a^{3m}\mid m\geq 1\;\\}$ belongs to
$\mathit{RL}_{1}^{V}\setminus\mathit{SLT}$.

######  Proof 2.16.

The language $L_{8}$ is generated by the right-linear grammar
$G=(\\{S\\},\\{a\\},\\{S\rightarrow a^{3}S,\ S\rightarrow a^{3}\\},S)$. Hence,
$L_{8}\in\mathit{RL}_{1}^{V}$.

Assume that the language $L_{8}$ is generated by a strictly locally
$k$-testable grammar for some number $k\geq 1$. Then, $L_{8}$ has a
representation as $\textbf{\rm[}B,I,E,F\textbf{\rm]}$ with $B\cup I\cup\
E\subseteq\\{a\\}^{k}$ and $F\subseteq\\{a\\}^{{}\leq k-1}$. Since the word
$a^{3k}$ belongs to the language $L_{8}$, we obtain that $B$, $I$, and $E$
contain the word $a^{k}$. But then, also the word $a^{3k+1}$ belongs to the
language $L_{8}$ which is a contradiction.

######  Lemma 2.17.

For each natural number $n\geq 1$, let
$V_{n}=\\{a_{1},a_{2},\ldots,a_{n+1}\\}$ be an alphabet with $n+1$ pairwise
different letters and let
$L_{9,n}=\\{a_{1}\\}^{+}\\{a_{2}\\}^{+}\cdots\\{a_{n+1}\\}^{+}$. Then, for
$n\geq 1$, the language $L_{9,n}$ belongs to the set
$\mathit{SLT}_{2}\setminus\mathit{RL}_{n}^{V}$.

######  Proof 2.18.

The language $L_{9,n}$ can be represented as

$L_{9,n}=\textbf{\rm[}\\{a_{1}a_{1},a_{1}a_{2}\\},\\{\;a_{p}a_{p}\mid 1\leq
p\leq n+1\;\\}\cup\\{\;a_{p}a_{p+1}\mid 1\leq p\leq
n\;\\},\\{a_{n}a_{n+1},a_{n+1}a_{n+1}\\},\emptyset\textbf{\rm]}.$

Hence, $L_{9,n}\in\mathit{SLT}_{2}$ for $n\geq 1$.

For generating a language $L_{9,n}$ for some number $n\geq 1$, at least a non-
terminal symbol is necessary for every letter $a_{i}$ ($1\leq i\leq n+1$).
Hence, $L_{9,n}\notin\mathit{RL}_{n}^{V}$.

We now prove inclusion relations and incomparabilities.

######  Lemma 2.19.

The class $\mathit{SLT}_{1}$ is properly included in the class
$\mathit{REG}_{5}^{Z}$.

######  Proof 2.20.

We first prove the inclusion $\mathit{SLT}_{1}\subseteq\mathit{REG}_{5}^{Z}$.

Let $L$ be a strictly locally 1-testable language. Then
$L=\textbf{\rm[}B,I,E,F\textbf{\rm]}$ with $B\subseteq V$, $I\subseteq V$,
$E\subseteq V$, and $F\subseteq\\{\lambda\\}$. We construct the following
deterministic finite automaton:

$A=(V,\\{z_{0},z_{1},\ldots,z_{4}\\},z_{0},Z_{\mathrm{f}},\delta)$

where

$Z_{\mathrm{f}}=\\{z_{1},z_{2}\\}\cup\begin{cases}\\{z_{0}\\},&\text{if
$\lambda\in F$},\\\ \emptyset,&\text{otherwise},\end{cases}$

and the transition function $\delta$ is given by the following diagram
($z_{0}$ is an accepting state if and only if $\lambda\in F$):

$z_{0}$start$z_{1}$$z_{2}$$z_{3}$$z_{4}$$B\cap E$$B\setminus E$$V\setminus
B$$I\setminus E$$E\setminus I$$V\setminus(E\cup I)$$E\cap I$$V$$E\cap
I$$E\setminus I$$V\setminus(E\cup I)$$I\setminus E$$V$

Due to space reasons, we leave the proof that $L(A)=L$ to the reader. From the
construction follows the inclusion
$\mathit{SLT}_{1}\subseteq\mathit{REG}_{5}^{Z}$.

A witness language for the properness of this inclusion is the language
$L_{1}=\\{a\\}^{*}\\{b\\}\\{a,b\\}^{*}$ from Lemma 2.1.

######  Lemma 2.21.

The class $\mathit{SLT}_{1}$ is incomparable to the classes
$\mathit{REG}_{i}^{Z}$ for $i\in\\{2,3,4\\}$.

######  Proof 2.22.

Due to the inclusion relations, it suffices to show that there is a language
in the set $\mathit{REG}_{2}^{Z}\setminus\mathit{SLT}_{1}$ and a language in
the set $\mathit{SLT}_{1}\setminus\mathit{REG}_{4}^{Z}$. A language for the
first case is $L_{1}=\\{a\\}^{*}\\{b\\}\\{a,b\\}^{*}$ as shown in Lemma 2.1. A
language for the second case is
$L_{2}=\textbf{\rm[}\\{a,b\\},\\{b,c\\},\\{a,c\\},\emptyset\textbf{\rm]}$ as
shown in Lemma 2.3.

######  Lemma 2.23.

The classes $\mathit{SLT}_{k}$ for $k\geq 2$ and $\mathit{SLT}$ are
incomparable to the classes $\mathit{REG}_{n}^{Z}$ for $n\geq 2$.

######  Proof 2.24.

Due to the inclusion relations, it suffices to show that there is a language
in the set $\mathit{REG}_{2}^{Z}\setminus\mathit{SLT}$ and a language in each
set $\mathit{SLT}_{2}\setminus\mathit{REG}_{n}^{Z}$ for $n\geq 2$. A language
for the first case is $L_{1}=\\{a\\}^{*}\\{b\\}\\{a,b\\}^{*}$ as shown in
Lemma 2.1. Languages for the second case are $L_{3,n}=\\{a_{1}a_{2}\ldots
a_{n-1}\\}$ as shown in Lemma 2.5.

######  Lemma 2.25.

The classes $\mathit{SLT}_{k}$ for $k\geq 1$ are incomparable to the classes
$\mathit{RL}_{n}^{P}$ for $n\geq 1$.

######  Proof 2.26.

Due to the inclusion relations, it suffices to show that there is a language
in the set $\mathit{RL}_{1}^{P}\setminus\mathit{SLT}_{k}$ for every $k\geq 1$
and a language in each set $\mathit{SLT}_{1}\setminus\mathit{RL}_{n}^{P}$ for
$n\geq 1$. Languages for the first case are $L_{4,k}=\\{a^{k}\\}$ for $k\geq
1$ as shown in Lemma 2.7. Languages for the second case are
$L_{5,n}=\\{a_{1},a_{2},\ldots,a_{n}\\}^{*}$ as shown in Lemma 2.9.

######  Lemma 2.27.

The class $\mathit{SLT}_{1}$ is properly included in the class
$\mathit{RL}_{2}^{V}$.

######  Proof 2.28.

Let $L=\textbf{\rm[}B,I,E,F\textbf{\rm]}$ be a strictly locally 1-testable
language over an alphabet $T$. We construct a right-linear grammar
$G=(\\{S,S^{\prime}\\},T,P,S)$ with the rules

  * •

$S\rightarrow w$ for every word $w\in F\cup(B\cap E)$,

  * •

$S\rightarrow wS^{\prime}$ for every word $w\in B$,

  * •

$S^{\prime}\rightarrow wS^{\prime}$ for every word $w\in I$, and

  * •

$S^{\prime}\rightarrow w$ for every word $w\in E$.

The language $L(G)$ generated is $F\cup(B\cap E)\cup(BI^{*}E)$ which is $L$.
Hence, $L\in\mathit{RL}_{2}^{V}$ and
$\mathit{SLT}_{1}\subseteq\mathit{RL}_{2}^{V}$. A witness language for the
properness of the inclusion is $L_{6}=\\{a\\}$ for which was proved in Lemma
2.11 that it belongs to the set $\mathit{RL}_{1}^{V}$ and therefore also to
$\mathit{RL}_{2}^{V}$ but not to $\mathit{SLT}_{1}$.

######  Lemma 2.29.

The class $\mathit{SLT}_{1}$ is incomparable to the class
$\mathit{RL}_{1}^{V}$.

######  Proof 2.30.

There is a language in the set $\mathit{RL}_{1}^{V}\setminus\mathit{SLT}_{1}$,
namely $L_{6}=\\{a\\}$ as shown in Lemma 2.11, and a language in the set
$\mathit{SLT}_{1}\setminus\mathit{RL}_{1}^{V}$, namely
$L_{7}=\\{a\\}\\{b\\}^{*}\\{a\\}\cup\\{a\\}$ as shown in Lemma 2.13.

######  Lemma 2.31.

The classes $\mathit{SLT}_{k}$ for $k\geq 2$ and $\mathit{SLT}$ are
incomparable to the classes $\mathit{RL}_{n}^{V}$ for $n\geq 1$.

######  Proof 2.32.

Due to the inclusion relations, it suffices to show that there is a language
in the set $\mathit{RL}_{1}^{V}\setminus\mathit{SLT}$ and a language in the
set $\mathit{SLT}_{2}\setminus\mathit{RL}_{n}^{V}$ for every number $n\geq 1$.
A language for the first case is $L_{8}=\\{\;a^{3m}\mid m\geq 1\;\\}$ as shown
in Lemma 2.15. A language for the second case is
$L_{9,n}=\\{a_{1}\\}^{+}\\{a_{2}\\}^{+}\cdots\\{a_{n+1}\\}^{+}$ as shown in
Lemma 2.17.

A summary of the inclusion relations is given in Figure 1. An edge label in
this figure refers to the paper or lemma above where the respective inclusion
is proved.

$\mathit{REG}$$\mathit{PS}$$\mathit{NC}$$\mathit{ORD}$$\mathit{DEF}$$\mathit{COMB}$$\mathit{NIL}$$\mathit{FIN}$$\mathit{SUF}$$\mathit{COMM}$$\mathit{CIRC}$$\mathit{SLT}_{1}$$\mathit{SLT}_{2}$$\vdots$$\mathit{SLT}$$\mathit{RL}_{1}^{V}$$\mathit{RL}_{2}^{V}$$\vdots$$\mathit{REG}_{2}^{Z}$$\vdots$$\mathit{REG}_{5}^{Z}$$\vdots$$\mathit{RL}_{1}^{P}$$\mathit{RL}_{2}^{P}$$\mathit{RL}_{3}^{P}$$\mathit{RL}_{4}^{P}$$\vdots$$\mathit{UF}$$\mathit{REG}_{1}^{Z}$$\mathit{MON}$[32][29][29][29][29][29][29][11][29][29][29][29][29][29][29][29][29][29][29][29][29][29][29][32][29][14][29][29][11][22][11]2.192.27[22][22][19][26][15][11][29][27][15][15][15][15][15]

Figure 1: Hierarchy of subregular language families

######  Theorem 2.33.

The inclusion relations presented in Figure 1 hold. An arrow from an entry $X$
to an entry $Y$ depicts the proper inclusion $X\subset Y$; if two families are
not connected by a directed path, then they are incomparable.

###  2.5 Tree-controlled grammars

A tree-controlled grammar is a quintuple $G=(N,T,P,S,R)$ where

  * •

$(N,T,P,S)$ is a context-free grammar with a set $N$ of non-terminal symbols,
a set $T$ of terminal symbols, a set $P$ of context-free non-erasing rules
(with the only exception that the rule $S\rightarrow\lambda$ is allowed if $S$
does not occur on a right-hand side of a rule), and an axiom $S$,

  * •

$R$ is a regular set over $N\cup T$.

The language $L(G)$ generated by a tree-controlled grammar $G=(N,T,P,S,R)$
consists of all such words $z\in T^{*}$ which have a derivation tree $t$ where
$z$ is the word obtained by reading the leaves from left to right and the
words of all levels of $t$ – besides the last one – belong to the regular
control language $R$.

Let ${\cal F}$ be a subfamily of $\mathit{REG}$. Then, we denote the family of
languages generated by tree-controlled grammars $G=(N,T,P,S,R)$ with
$R\in{\cal F}$ by ${{\cal TC}}({\cal F})$.

######  Example 2.34.

As an example, we consider the tree-controlled grammar

$G_{1}=(\\{S\\},\\{a\\},\\{S\rightarrow SS,S\rightarrow a\\},S,\\{S\\}^{*}).$

Since the terminal symbol $a$ is not allowed to appear before the last level,
on all levels before, any occurrence of $S$ is replaced by $SS$. Finally, any
letter $S$ is replaced by $a$. Therefore, the levels of an allowed derivation
tree consist of the words $S$, $SS$, $SSSS$, $\dots$, $S^{2^{n}}$, $a^{2^{n}}$
for some $n\geq 0$. Thus, $L(G_{1})=\\{\;a^{2^{n}}\mid n\geq 0\;\\}$. Due to
the structure of the control language which is monoidal and can be generated
by a grammar with one non-terminal symbol and two rules, we further obtain

$L(G_{1})\in{\cal TC}(\mathit{MON})\cap{\cal TC}(\mathit{RL}_{1}^{V})\cap{\cal
TC}(\mathit{RL}_{2}^{P}).$

######  Example 2.35.

We now consider the tree-controlled grammar

$G_{2}=(\\{S,A,B,C\\},\\{a,b,c\\},P,S,\\{S,aAbBcC\\})$

with

$P=\\{S\rightarrow aAbBcC,A\rightarrow aA,B\rightarrow bB,C\rightarrow
cC,A\rightarrow a,B\rightarrow b,C\rightarrow c\\}.$

By the definition of the control language, any derivation in $G_{2}$ has the
form

$S\Longrightarrow aAbBcC\Longrightarrow
aaAbbBccC\Longrightarrow\dots\Longrightarrow
a^{n-1}Ab^{n-1}Bc^{n-1}C\Longrightarrow a^{n}b^{n}c^{n}$

with $n\geq 2$. Thus, the tree-controlled grammar $G_{2}$ generates the non-
context-free language

$L(G_{2})=\\{a^{n}b^{n}c^{n}\\}{n\geq 2}.$

Due to the structure of the control language which is finite and can be
generated by a grammar with one non-terminal symbol and two rules, we further
obtain

$L(G_{2})\in{\cal TC}(\mathit{FIN})\cap{\cal TC}(\mathit{RL}_{1}^{V})\cap{\cal
TC}(\mathit{RL}_{2}^{P}).$

In [21] (see also [6]), it has been shown that a language $L$ is generated by
a tree-controlled grammar if and only if it is generated by a context-
sensitive grammar.

######  Theorem 2.36.

([21], [6]) It holds ${{\cal TC}}(\mathit{REG})=\mathit{CS}$.

In subsequent papers, tree-controlled grammars have been investigated where
the control language belongs to some subfamily of the class $\mathit{REG}$
([7, 8, 9, 10, 28, 30, 31]). In this paper, we continue this research with
further subregular language families.

From the definition follows that the subset relation is preserved under the
use of tree-controlled grammars: if we allow more, we do not obtain less.

######  Lemma 2.37.

For any two language classes $X$ and $Y$ with $X\subseteq Y$, we have the
inclusion

${\cal TC}(X)\subseteq{\cal TC}(Y).$

A summary of the inclusion relations known so far is given in Figure 2. An
arrow from an entry $X$ to an entry $Y$ depicts the inclusion $X\subseteq Y$;
a solid arrow means proper inclusion; a dashed arrow indicates that it is not
known whether the inclusion is proper. If two families are not connected by a
directed path, then they are not necessarily incomparable. An edge label in
this figure refers to the paper where the respective inclusion is proved.

$\mathit{CF}$$\mathit{E0L}\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasTru-
afl08}{}{}]}}}}}{{=}}{\cal
TC}(\mathit{MON}_{1})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasStiTru-
dcfs08-tcs}{}{}]}}}}}{{=}}{\cal TC}(\mathit{REG}_{1}^{Z})$${\cal
TC}(\mathit{COMB})$${\cal
TC}(\mathit{FIN})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasTru-
afl08}{}{}]}}}}}{{=}}\mathit{MAT}_{\mathit{fin}}$${\cal
TC}(\mathit{NIL})$${\cal TC}(\mathit{DEF})$${\cal
TC}(\mathit{REG}_{2}^{Z})$${\cal TC}(\mathit{MON}_{{}\geq
2})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasStiTru-
dcfs08-tcs}{}{}]}}}}}{{=}}\mathit{ET0L}$${\cal
TC}(\mathit{COMM})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasTru-
afl08}{}{}]}}}}}{{=}}\mathit{MAT}$${\cal TC}(\mathit{REG}_{4}^{Z})$
$\mathit{CS}\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{Pau79-tc}{}{}]}}}}}{{=}}{\cal
TC}(\mathit{REG})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasTru-
afl08}{}{}]}}}}}{{=}}{\cal
TC}(\mathit{CIRC})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasTru-
afl08}{}{}]}}}}}{{=}}{\cal TC}(\mathit{SUF})$
$\phantom{\mathit{CS}}\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasTru-
afl08}{}{}]}}}}}{{=}}{\cal
TC}(\mathit{ORD})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasTru-
afl08}{}{}]}}}}}{{=}}{\cal
TC}(\mathit{NC})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasTru-
afl08}{}{}]}}}}}{{=}}{\cal
TC}(\mathit{PS})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasStiTru-
dcfs08-tcs}{}{}]}}}}}{{=}}{\cal TC}(\mathit{REG}_{{}\geq 5}^{Z})$
[23][8][10][10][6][23][6][7][6]

Figure 2: Hierarchy of subregularly tree-controlled language families

##  3 Results

We insert the classes ${\cal TC}(SLT_{k})$ for $k\geq 1$, ${\cal
TC}(\mathit{SLT})$, ${\cal TC}(\mathit{RL}_{n}^{V})$ for $n\geq 1$, and ${\cal
TC}(\mathit{RL}_{n}^{P})$ for $n\geq 1$ into the existing hierachy (see Figure
2).

The inclusions follow from the inclusion relations of the respective families
of the control languages (see Figure 1 and Lemma 2.37).

In most cases, we obtain that any context-sensitive language can be generated
by a tree-controlled grammar where the control language is taken from that
family.

######  Theorem 3.1.

We have ${\cal TC}(\mathit{SLT}_{k})=\mathit{CS}$ for $k\geq 2$ and ${\cal
TC}(\mathit{SLT})=\mathit{CS}$.

######  Proof 3.2.

Let $L$ be a context-sensitive language. Then, there is a context-sensitive
grammar $G=(N,T,P,S)$ with $L(G)=L$ which is in Kuroda normal form, where the
rule set $P$ can be divided into two sets $P_{1}$ and $P_{2}$ such that all
rules of $P_{1}$ are of the form $A\rightarrow BC$ or $A\rightarrow B$ or
$A\rightarrow a$ with $A,B,C,D\in N$ and $a\in T$ and all rules of $P_{2}$ are
of the form $AB\rightarrow CD$ with $A,B,C,D\in N$.

We will construct a tree-controlled grammar $G_{\mathrm{tc}}$ which simulates
the grammar $G$. Since $G_{\mathrm{tc}}$ has only context-free rules, the non-
context-free rules of $G$ have to be substituted by context-free rules and
some control such that the parts of a non-context-free rule which are
independent from the view of the core grammar of $G_{\mathrm{tc}}$ remain
connected.

We label the non-context-free rules and associate the non-terminal symbols of
their left-hand sides with new non-terminal symbols which are marked with the
rule label and the position (first or second letter). The context-free rules
can be freely applied also in the tree-controlled grammar. A non-context-free
rule $p:AB\rightarrow CD$ will be simulated by context-free rules

$A\rightarrow A_{p,1},\ B\rightarrow B_{p,2},\ A_{p,1}\rightarrow C,\mbox{ and
}B_{p,2}\rightarrow D.$

The control language ensures that the rules which belong together (here
$A\rightarrow A_{p,1}$ and $B\rightarrow B_{p,2}$) are applied together (at
the same time and next to each other). If a terminal symbol is produced in a
sentential form of the grammar $G$, then it remains there until the whole
terminal word is produced. In the tree-controlled grammar $G_{\mathrm{tc}}$,
one has to keep track of terminal symbols because they ‘disappear’ (once
produced, they are not present in the next level anymore) and then two non-
terminal symbols appear next to each other, although they are not neighbours
in the sentential form. So, the tree-controlled grammar should produce
placeholders for terminal symbols and replace them by the actual terminal
symbols only in the very end. In a tree-controlled grammar, from one level to
the next, all non-terminal symbols are replaced. This can be seen as some kind
of shortcut where production rules which are independent from each other are
applied in parallel.

We construct such a tree-controlled grammar
$G_{\mathrm{tc}}=(N_{\mathrm{tc}},T,P_{\mathrm{tc}},S,R_{\mathrm{tc}})$. The
terminal alphabet and start symbol are the same as in the grammar $G$. We now
give the rules; the non-terminal symbols will be collected later from the
rules. At the end, we will give the control language $R_{\mathrm{tc}}$.

In order to simulate the context-free rules directly, we take all non-
terminating rules of them from $G$ as they are:

$P_{\mathrm{cf}}=P\cap(\\{\;A\rightarrow BC\mid A,B,C\in
N\;\\}\cup\\{\;A\rightarrow B\mid A,B\in N\;\\}).$

Instead of the terminating rules, we take rules with a placeholder (for each
terminal symbol $a$, we introduce a unique non-terminal symbol $\hat{a}$), but
finally, those placeholders have to be terminated:

$P_{\mathrm{t}}=\\{\;A\rightarrow\hat{a}\mid A\in N,a\in T,A\rightarrow a\in
P\;\\}\cup\\{\;\hat{a}\rightarrow a\mid a\in T\;\\}.$

We give also rules which can delay the derivation such that not everything
needs to be replaced in parallel:

$P_{\mathrm{d}}=\\{\;A\rightarrow A\mid A\in
N\;\\}\cup\\{\;\hat{a}\rightarrow\hat{a}\mid a\in T\;\\}.$

For simulating the non-context-free rules, first rules are applied which mark
the position of the intended application such that the control language has
the chance to check whether the plan is alright (if it is not, then the
derivation will block). In the next step, the markers will be replaced by
their actual target non-terminal symbols:

$P_{\mathrm{cs}}=\bigcup_{p:AB\rightarrow CD\in P}\\{A\rightarrow A_{p,1},\
B\rightarrow B_{p,2},\ A_{p,1}\rightarrow C,\ B_{p,2}\rightarrow D\\}.$

Other rules are not needed, hence,

$P_{\mathrm{tc}}=P_{\mathrm{cf}}\cup P_{\mathrm{t}}\cup P_{\mathrm{d}}\cup
P_{\mathrm{cs}}.$

The set $N_{\mathrm{tc}}$ of non-terminal symbols results as follows:

$\displaystyle N_{\mathrm{cf}}=N\cup\\{\;\hat{a}\mid a\in T\;\\},\
N_{1}=\\{\;A_{p,1}\mid p:AB\rightarrow CD\in P\;\\},\ N_{2}=\\{\;B_{p,2}\mid
p:AB\rightarrow CD\in P\;\\},$ $\displaystyle N_{12}=\\{\;A_{p,1}B_{p,2}\mid
p:AB\rightarrow CD\in P\;\\},\ N_{\mathrm{tc}}=N_{\mathrm{cf}}\cup N_{1}\cup
N_{2}.$

A derivation can go wrong only if the simulation of a non-context-free rule is
not properly planned. Hence, as control language, we take

$R_{\mathrm{tc}}=(N_{\mathrm{cf}}\cup N_{12})^{*}.$

Since the context-free rules of the grammar $G$ can be applied independently
from each other and do not have to be applied at a certain time (thanks to the
rules from the subset $P_{\mathrm{d}}$) and the correct simulation of the non-
context-free rules is ensured by the control language $R_{\mathrm{tc}}$, it is
not hard to see that the generated languages $L(G)$ and $L(G_{\mathrm{tc}})$
coincide.

The control language $R_{\mathrm{tc}}$ is strictly locally 2-testable as can
be seen from the following representation: Let

$\displaystyle B$ $\displaystyle=N_{\mathrm{cf}}^{2}\cup
N_{\mathrm{cf}}N_{1}\cup N_{12},$ $\displaystyle I$
$\displaystyle=N_{\mathrm{cf}}^{2}\cup N_{\mathrm{cf}}N_{1}\cup N_{12}\cup
N_{2}N_{\mathrm{cf}}\cup N_{2}N_{1},$ $\displaystyle E$
$\displaystyle=N_{\mathrm{cf}}^{2}\cup N_{12}\cup N_{2}N_{\mathrm{cf}},$
$\displaystyle F$ $\displaystyle=N_{\mathrm{cf}}\cup\\{\lambda\\}.$

Then $R_{\mathrm{tc}}=\textbf{\rm[}B,I,E,F\textbf{\rm]}$.

Altogether, we obtain $\mathit{CS}\subseteq{\cal
TC}(\mathit{SLT}_{2})\subseteq{\cal TC}(\mathit{SLT}_{k})\subseteq{\cal
TC}(\mathit{SLT})\subseteq\mathit{CS}$ for $k\geq 3$. Thus, it holds ${\cal
TC}(\mathit{SLT}_{k})=\mathit{CS}$ for $k\geq 2$ and ${\cal
TC}(\mathit{SLT})=\mathit{CS}$.

######  Theorem 3.3.

We have ${\cal TC}(\mathit{RL}_{n}^{V})=\mathit{CS}$ for $n\geq 1$.

######  Proof 3.4.

The control language $R_{\mathrm{tc}}=(N_{\mathrm{cf}}\cup N_{12})^{*}$ from
the tree-controlled grammar $G_{\mathrm{tc}}$ in the proof of Theorem 3.1 can
be generated by a right-linear grammar
$G^{\prime}=(\\{S^{\prime}\\},N_{\mathrm{tc}},P^{\prime},S^{\prime})$ where

$P^{\prime}=\\{\;S^{\prime}\rightarrow xS^{\prime}\mid x\in
N_{\mathrm{cf}}\cup N_{12}\;\\}\cup\\{\;S^{\prime}\rightarrow x\mid x\in
N_{\mathrm{cf}}\cup N_{12}\;\\}.$

Hence, $\mathit{CS}\subseteq{\cal TC}(\mathit{RL}_{1}^{V})\subseteq{\cal
TC}(\mathit{RL}_{n}^{V})\subseteq\mathit{CS}$ for $n\geq 2$. Thus, we conclude
${\cal TC}(\mathit{RL}_{n}^{V})=\mathit{CS}$ for $n\geq 1$.

From the proof of Theorem 3.1, we conclude also the following statement.

######  Theorem 3.5.

We have ${\cal TC}(\mathit{UF})=\mathit{CS}$.

######  Proof 3.6.

Let $L=\\{w_{1},w_{2},\ldots,w_{n}\\}$ be a finite language. Then
$L^{*}=(\\{w_{1}\\}^{*}\\{w_{2}\\}^{*}\cdots\\{w_{n}\\}^{*})^{*}$ and is
therefore union-free.

The control language $R_{\mathrm{tc}}=(N_{\mathrm{cf}}\cup N_{12})^{*}$ from
the tree-controlled grammar $G_{\mathrm{tc}}$ in the proof of Theorem 3.1 is
the Kleene closure of a finite language and, hence, it is union-free.

Regarding the classes ${\cal TC}(\mathit{RL}_{n}^{P})$ for $n\geq 1$, the
situation is different since the number of rules depends on the size of the
alphabet (which is not necessarily the case for the number of non-terminal
symbols or the number of states).

If the control language is generated with one rule only, then either the
control language is the empty set (if the right-hand side of the rule contains
a non-terminal symbol) or it contains exactly one terminal word. Since the
start symbol of the tree-controlled grammar always forms the first level of
the derivation tree, it must be contained in the control language (otherwise,
the derivation would be blocked right from the beginning). Therefore, we
obtain the following result.

######  Lemma 3.7.

Let $G=(N,T,P,S,R)$ a tree-controlled grammar with $R\in\mathit{RL}_{1}^{P}$.
Then, the generated language is

$L(G)=\begin{cases}\\{\;w\mid w\in T^{*}\mbox{ and }S\rightarrow w\in
P\;\\},&\text{if $R=\\{S\\}$},\\\ \emptyset,&\text{otherwise}.\end{cases}$

######  Proof 3.8.

If $R=\\{S\\}$, then every level but the last one of the derivation tree is
$S$ and the last level is a terminal word which is produced by $S$. On the
other hand, all terminal words derived from $S$ belong to the generated
language.

If $R\not=\\{S\\}$, then $S\notin R$ since $R$ contains at most one word
because $R\in\mathit{RL}_{1}^{P}$. Since $S$ is the word of the first level of
the derivation tree, there is no derivation possible. Hence, $L(G)$ is empty.

From this result, the next one immediately follows.

######  Theorem 3.9.

We have ${\cal TC}(\mathit{RL}_{1}^{P})=\mathit{FIN}$.

######  Proof 3.10.

The inclusion ${\cal TC}(\mathit{RL}_{1}^{P})\subseteq\mathit{FIN}$ follows
from Lemma 3.7. The inclusion $\mathit{FIN}\subseteq{\cal
TC}(\mathit{RL}_{1}^{P})$ can also be seen from Lemma 3.7: Let $L$ be a finite
language over an alphabet $T$. Then, construct a tree-controlled grammar
$G=(\\{S\\},T,\\{\;S\rightarrow w\mid w\in L\;\\},S,\\{S\\})$. It holds
$L(G)=L$ and $L(G)\in{\cal TC}(\mathit{RL}_{1}^{P})$.

If the control language is taken from the family ${\cal
TC}(\mathit{RL}_{2}^{P})$, then already context-sensitive languages can be
generated as the Examples 2.34 and 2.35 show.

######  Theorem 3.11.

We have ${\cal TC}(\mathit{RL}_{1}^{P})\subset{\cal TC}(\mathit{RL}_{2}^{P})$.

######  Proof 3.12.

The inclusion follows from Theorem 2.33 and Lemma 2.37. According to Theorem
3.9, the family ${\cal TC}(\mathit{RL}_{1}^{P})$ contains finite languages
only. As shown in the Examples 2.34 and 2.35, the family ${\cal
TC}(\mathit{RL}_{2}^{P})$ contains non-context-free languages.

A summary of all the inclusion relations is given in Figure 3. An arrow from
an entry $X$ to an entry $Y$ depicts the inclusion $X\subseteq Y$; a solid
arrow means proper inclusion; a dashed arrow indicates that it is not known
whether the inclusion is proper. If two families are not connected by a
directed path, then they are not necessarily incomparable. An edge label in
this figure refers to the paper or theorem above where the respective
inclusion is proved.

${\cal
TC}(\mathit{RL}_{1}^{P})\stackrel{{\scriptstyle\mbox{\footnotesize{\ref{thm-p1}}}}}{{=}}\mathit{FIN}$$\mathit{CF}$$\mathit{E0L}\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasTru-
afl08}{}{}]}}}}}{{=}}{\cal
TC}(\mathit{MON}_{1})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasStiTru-
dcfs08-tcs}{}{}]}}}}}{{=}}{\cal TC}(\mathit{REG}_{1}^{Z})$${\cal
TC}(\mathit{COMB})$${\cal
TC}(\mathit{FIN})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasTru-
afl08}{}{}]}}}}}{{=}}\mathit{MAT}_{\mathit{fin}}$${\cal
TC}(\mathit{NIL})$${\cal TC}(\mathit{DEF})$${\cal TC}(\mathit{SLT}_{1})$${\cal
TC}(\mathit{REG}_{2}^{Z})$${\cal TC}(\mathit{MON}_{{}\geq
2})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasStiTru-
dcfs08-tcs}{}{}]}}}}}{{=}}\mathit{ET0L}$${\cal
TC}(\mathit{COMM})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasTru-
afl08}{}{}]}}}}}{{=}}\mathit{MAT}$${\cal TC}(\mathit{REG}_{4}^{Z})$${\cal
TC}(\mathit{RL}_{2}^{P})$${\cal TC}(\mathit{RL}_{n}^{P})$
$\mathit{CS}\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{Pau79-tc}{}{}]}}}}}{{=}}{\cal
TC}(\mathit{REG})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasTru-
afl08}{}{}]}}}}}{{=}}{\cal
TC}(\mathit{CIRC})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasTru-
afl08}{}{}]}}}}}{{=}}{\cal TC}(\mathit{SUF})$
$\phantom{\mathit{CS}}\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasTru-
afl08}{}{}]}}}}}{{=}}{\cal
TC}(\mathit{ORD})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasTru-
afl08}{}{}]}}}}}{{=}}{\cal
TC}(\mathit{NC})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasTru-
afl08}{}{}]}}}}}{{=}}{\cal
TC}(\mathit{PS})\stackrel{{\scriptstyle\mbox{\footnotesize{\cite[cite]{[\@@bibref{}{DasStiTru-
dcfs08-tcs}{}{}]}}}}}{{=}}{\cal TC}(\mathit{REG}_{{}\geq 5}^{Z})$
$\phantom{\mathit{CS}}\stackrel{{\scriptstyle\mbox{\footnotesize{\ref{thm-uf-
cs}}}}}{{=}}{\cal
TC}(\mathit{UF})\stackrel{{\scriptstyle\mbox{\footnotesize{\ref{thm-
slt2-cs}}}}}{{=}}{\cal TC}(\mathit{SLT}_{{}\geq
2})\stackrel{{\scriptstyle\mbox{\footnotesize{\ref{thm-slt2-cs}}}}}{{=}}{\cal
TC}(\mathit{SLT})\stackrel{{\scriptstyle\mbox{\footnotesize{\ref{thm-rlv-
cs}}}}}{{=}}{\cal TC}(\mathit{RL}_{{}\geq 1}^{V})$
[23][8][24]3.11[10][10][6][23][6][7][6]

Figure 3: New Hierarchy of subregularly tree-controlled language families

##  4 Conclusion

There are several families of languages generated by tree-controlled grammars
where we do not have a characterization by some other language class. The
strictness of some inclusions and the incomparability of some families remain
as open problems.

In the present paper, we have only considered tree-controlled grammars without
erasing rules. For tree-controlled grammars where erasing rules are allowed,
several results have been published already (see, e. g., [8, 30, 31]). Also in
this situation, there are some open problems.

Another direction for future research is to consider other subregular language
families or to relate the families of languages generated by tree-controlled
grammars to language families obtained by other grammars/systems with
regulated rewriting.

## References

  * [1]
  * [2] Janusz A. Brzozowski (1962): _Regular Expression Techniques for Sequential Circuits_.  Ph.D. thesis, Princeton University, Princeton, NJ, USA.
  * [3] Janusz A. Brzozowski, Galina Jirásková & C. Zou (2014): _Quotient complexity of closed languages_.  Theory of Computing Systems 54, pp. 277–292, 10.1007/s00224-013-9515-7.
  * [4] Jürgen Dassow (1979): _On the circular closure of languages_.  Elektronische Informationsverarbeitung und Kybernetik/Journal of Information Processing and Cybernetics 15(1–2), pp. 87–94.
  * [5] Jürgen Dassow, Florin Manea & Bianca Truthe (2011): _On contextual grammars with subregular selection languages_.  In Markus Holzer, Martin Kutrib & Giovanni Pighizzini, editors: Descriptional Complexity of Formal Systems – 13th International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25 – 27, 2011. Proceedings, LNCS 6808, Springer-Verlag, pp. 135–146, 10.1007/978-3-642-22600-7_11.
  * [6] Jürgen Dassow & Gheorghe Păun (1989): _Regulated Rewriting in Formal Language Theory_.  EATCS Monographs in Theoretical Computer Science 18, Springer-Verlag, 10.1007/978-3-642-74932-2.
  * [7] Jürgen Dassow, Ralf Stiebe & Bianca Truthe (2009): _Two collapsing hierarchies of subregularly tree controlled languages_.  Theoretical Computer Science 410(35), pp. 3261–3271, 10.1016/j.tcs.2009.03.005.
  * [8] Jürgen Dassow, Ralf Stiebe & Bianca Truthe (2010): _Generative capacity of subregularly tree controlled grammars_.  International Journal of Foundations of Computer Science 21(5), pp. 723–740, 10.1142/S0129054110007520.
  * [9] Jürgen Dassow & Bianca Truthe (2008): _On two hierarchies of subregularly tree controlled languages_.  In Cezar Câmpeanu & Giovanni Pighizzini, editors: Descriptional Complexity of Formal Systems, 10th International Workshop, Charlottetown, Prince Edward Island, Canada, July 16–18, 2008, Proceedings, University of Prince Edward Island, pp. 145–156.
  * [10] Jürgen Dassow & Bianca Truthe (2008): _Subregularly tree controlled grammars and languages_.  In Erzsébet Csuhaj-Varjú & Zoltán Ésik, editors: Automata and Formal Languages, 12th International Conference, AFL 2008, Balatonfüred, Hungary, May 27–30, 2008, Proceedings, Computer and Automation Research Institute, Hungarian Academy of Sciences, pp. 158–169.
  * [11] Jürgen Dassow & Bianca Truthe (2022): _On the generative capacity of contextual grammars with strictly locally testable selection languages_.  In Henning Bordihn, Géza Horváth & György Vaszil, editors: 12th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2022), Debrecen, Hungary, August 26 – 27, 2022. Proceedings, EPTCS 367, Open Publishing Association, pp. 65–80, 10.4204/EPTCS.367.5.
  * [12] Ferenc Gécseg & István Peák (1972): _Algebraic Theory of Automata_.  Academiai Kiado, Budapest.
  * [13] Arthur Gill & Lawrence T. Kou (1974): _Multiple-entry finite automata_.  Journal of Computer and System Sciences 9(1), pp. 1–19, 10.1016/S0022-0000(74)80034-6.
  * [14] Ivan M. Havel (1969): _The theory of regular events II_.  Kybernetika 5(6), pp. 520–544.
  * [15] Markus Holzer & Bianca Truthe (2015): _On relations between some subregular language families_.  In Rudolf Freund, Markus Holzer, Nelma Moreira & Rogério Reis, editors: Seventh Workshop on Non-Classical Models of Automata and Applications (NCMA), Porto, Portugal, August 31 – September 1, 2015, Proceedings<EMAIL_ADDRESS>318, Österreichische Computer Gesellschaft, pp. 109–124.
  * [16] John E. Hopcroft & Jeffrey D. Ullman (1979): _Introduction to Automata Theory, Languages, and Computation_.  Addison-Wesley, Reading.
  * [17] Karel Čulik II & Hermann A. Maurer (1977): _Tree controlled grammars_.  Computing 19(2), pp. 129–139, 10.1007/BF02252350.
  * [18] Sige Yuki Kuroda (1964): _Classes of languages and linear bounded automata_.  Information and Control 7(2), pp. 207–223, 10.1016/S0019-9958(64)90120-2.
  * [19] Robert McNaughton & Seymour Papert (1971): _Counter-Free Automata_.  MIT Press, Cambridge, USA.
  * [20] Micha A. Perles, Michael O. Rabin & Eliahu Shamir (1963): _The theory of definite automata_.  IEEE Trans. Electronic Computers 12, pp. 233–243, 10.1109/PGEC.1963.263534.
  * [21] Gheorghe Păun (1979): _On the generative capacity of tree controlled grammars_.  Computing 21, pp. 213–220, 10.1007/BF02253054.
  * [22] Stefano Crespi Reghizzi & Pierluigi San Pietro (2011): _From regular to strictly locally testable languages_.  In Petr Ambrož, Štěpán Holub & Zuzana Masáková, editors: 8th International Conference WORDS 2011, EPTCS 63, pp. 103–111, 10.4204/EPTCS.63.14.
  * [23] Grzegorz Rozenberg & Arto Salomaa (1980): _The Mathematical Theory of L Systems_.  Academic Press.
  * [24] Grzegorz Rozenberg & Arto Salomaa, editors (1997): _Handbook of Formal Languages_.  Springer-Verlag, Berlin.
  * [25] Huei-Jan Shyr (1991): _Free Monoids and Languages_.  Hon Min Book Co., Taichung, Taiwan.
  * [26] Huei-Jan Shyr & Gabriel Thierrin (1974): _Ordered automata and associated languages_.  Tankang Journal of Mathematics 5(1), pp. 9–20.
  * [27] Huei-Jan Shyr & Gabriel Thierrin (1974): _Power-separating regular languages_.  Mathematical Systems Theory 8(1), pp. 90–95, 10.1007/BF01761710.
  * [28] Ralf Stiebe (2008): _On the complexity of the control language in tree controlled grammars_.  In Jürgen Dassow & Bianca Truthe, editors: Colloquium on the Occasion of the 50th Birthday of Victor Mitrana, Otto-von-Guericke-Universitäat Magdeburg, Germany, June 27, 2008, Proceedings, Otto-von-Guericke-Universitäat Magdeburg, Germany, pp. 29–36.
  * [29] Bianca Truthe (2018): _Hierarchy of Subregular Language Families_.  Technical Report, Justus-Liebig-Universität Giessen, Institut für Informatik, IFIG Research Report 1801.
  * [30] Sherzod Turaev, Jürgen Dassow, Florin Manea & Mohd Hasan Selamat (2012): _Language classes generated by tree controlled grammars with bounded nonterminal complexity_.  Theoretical Computer Science 449, pp. 134–144, 10.1016/j.tcs.2012.04.013.
  * [31] György Vaszil (2012): _On the nonterminal complexity of tree controlled grammars_.  In Henning Bordihn, Martin Kutrib & Bianca Truthe, editors: Languages Alive – Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday, LNCS 7300, Springer, pp. 265–272, 10.1007/978-3-642-31644-9_18.
  * [32] Barbara Wiedemann (1978): _Vergleich der Leistungsfähigkeit endlicher determinierter Automaten_.  Diplomarbeit, Universität Rostock.