# Quantum automata and languages of finite index ††thanks:

Andrea<EMAIL_ADDRESS>
Dipartimento di Matematica e Informatica “U. Dini”
Università di Firenze
Viale Giovanni Battista Morgagni 67/A, 50134 Firenze, Italy  Flavio
<EMAIL_ADDRESS>Paolo<EMAIL_ADDRESS>Dipartimento di Matematica “G. Castelnuovo”
Sapienza Università di Roma
Piazzale Aldo Moro 2, 00185 Roma, Italy

###### Abstract

This paper is a continuation of a previous study conducted in [7, 8] on the
so-called measure once finite quantum automata model introduced by Moore and
Crutchfield in 2000. We investigate conditions assuring that, given a language
recognized by such a device and a language generated by a context-free grammar
of finite index or by a matrix context-free grammar, it is recursively
decidable whether or not they have a nonempty intersection.

Keywords: Quantum automata, Context-free languages, Algebraic groups,
Decidability

AMS subject classifications: 81P68, 68Q45

##  1 Introduction

In this paper, we investigate an issue of decidability for quantum (finite)
automata. Quantum automata were introduced at the beginning of 2000’s in [23]
as a new model of language recognizer (cf. [5]). Numerous publications have
ever since compared their decision properties to those of other models and, in
particular, to probabilistic finite automata. In this theoretical setting, we
investigate the decidability of a problem for quantum automata introduced in
[6, 7], named Intersection Problem. The starting point of that investigation
is a result of Blondel, Jeandel, Koiran, and Portier which shows in [8] that,
given a (“measure-once” in the sense of [23]) quantum automaton $\cal Q$, it
is decidable whether the language recognized by $\cal Q$ has a non trivial
intersection with the free monoid generated by the input alphabet of $\cal Q$
(Emptiness problem).

It is worth remarking that these problems are strictly related to some
computational issues concerning matrices. Precisely, a crucial step in the
construction of the decision procedure for both the Emptiness and Intersection
Problem amounts to effectively compute the Zariski closure of a finitely
generated group of matrices over $\mathbb{Q}$. For that task, an appropriate
algorithm has been developed in [12] by Derksen, Jeandel, and Koiran.

Before coming back to the Intersection Problem, we find then convenient to
recall some developments of the research on that aspect. Two striking results
have been obtained in the recent past years in connection with Derksen et al.
algorithm. In 2022 Nosan, Pouly, Schmitz, Shirmohammadi, and Worrell,
following an alternative approach for such computation, have obtained in [25]
a bound on the degree of the polynomials that define the Zariski closure of
the set and showed that the latter can be computed in elementary time.

The second was obtained in 2023 by Hrushovski, Ouaknine, Pouly, and Worrel for
the study of the effective computation of polynomial invariants for affine
programs [17]. Precisely, it is exhibited an algorithm that, given a finite
set of square matrices of the same size with coefficients in $\mathbb{Q}$,
computes the Zariski closure of the semigroup generated by the set.

It should be pointed out that the decidability issues for matrix semigroups is
a challenge problem. Even in small size, a well-known result by Paterson shows
that the problem of freeness and that of membership are both undecidable for
matrix semigroups over $\mathbb{Z}$ of size $3$ (cf [9]). In contrast, in
2017, a surprising result of Potapov and Semukhin [28] shows that the
membership is decidable for non-singular matrix integer semigroups of size
$2$. We now come back to the Intersection Problem and give a formal
presentation of our work. A _finite quantum automaton_ (in the sense of [23])
is a quadruple

${\cal Q}=(s,\varphi,P,\lambda),$ (1)

where $s\in\mathbb{R}^{n}$ is a row-vector of unit Euclidean norm, $P$ is a
projection matrix of $\mathbb{R}^{n}$, $\varphi:\Sigma^{*}\rightarrow O_{n}$
is a morphism from the free monoid $\Sigma^{*}$, generated by the input
alphabet $\Sigma$ of $\cal Q$, into the group $O_{n}$ of _orthogonal_ $n\times
n$-matrices over $\mathbb{R}$ and the _threshold_ $\lambda$ has value in
$\mathbb{R}$.

We are mainly interested in effective properties which require the quantum
automaton to be effectively given. We thus consider the model of _rational
quantum automaton_ , i.e., where all the coefficients of the components of (1)
and $\lambda$ are rational numbers. For a real threshold $\lambda$, the
languages recognized by $\cal Q$ with strict and nonstrict threshold $\lambda$
are

$|{\cal Q}_{>}|=\\{w\in\Sigma^{*}\mid||s\varphi(w)P||>\lambda\\},\quad|{\cal
Q}_{\geq}|=\\{w\in\Sigma^{*}\mid||s\varphi(w)P||\geq\lambda\\},$

where $||\cdot||$ denotes the Euclidean norm of vectors. Let ${\cal L}$ be a
family of effectively defined languages. The problem we tackle is thus the
following:

$(L,{\cal Q})$ Intersection

Input: a language $L$ in a family ${\cal L}$ of languages and a rational
quantum automaton ${\cal Q}$.

Question: does $L\cap|{\cal Q}_{>}|=\emptyset$ hold?

As already pointed out, it has been proven in [8] the decidability of the
problem in the specific case $L$ $=\Sigma^{*}$. This result contrasts with the
corresponding problems (strict and non strict, respectively) for probabilistic
finite automata. Indeed for this class of automata, the Emptiness problems
w.r.t. $|{\cal Q}_{>}|$ and $|{\cal Q}_{\geq}|$ are both undecidable (see
[27], Thm 6.17). Also it contrasts with the undecidability of the Emptiness
problem of $|{\cal Q}_{\geq}|$ for quantum automata [8]. It is also proven in
[21] that both the problems (strict and non strict, respectively) remain
undecidable for the “measure many” model of quantum automata, a model not
computationally equivalent to the “measure once”, introduced by Kondacs and
Watrous in [22].

In order to describe the main contributions of the paper, it may be useful to
recall some lines of the technique used in the proof of the Intersection
Problem in [7]. For this purpose, following the same strategy of [8], we first
observe that the Intersection Problem is equivalent to the inclusion

$\varphi(L)\subseteq|{\cal Q}_{\leq}|.$ (2)

Since the function

$M\rightarrow||sMP||,$

– where $M$ is an arbitrary matrix in $\mathbb{R}^{n\times n}$, and $s,P$ are
components of (1) – is continuous, it is sufficient to prove that, for all
matrices $M$ in the Euclidean closure ${\mathbf{C}l}(\varphi(L))$ of
$\varphi(L)$, the condition $||sMP||\leq\lambda$ holds (see Section 3). Such
condition is then effectively tested by running, in parallel, two
semialgorithms. The first tests the inclusion $\varphi(L)\subseteq|{\cal
Q}_{>}|$ and it is readily seen to be semidecidable. The second, which is the
main bulk, is to prove that (2) is semidecidable.

The semidecidability of the latter procedure is achieved by expressing the
property (2) in first-order logic of the field of reals, which, in turn,
consists to effectively compute a representation of
${\mathbf{C}l}(\varphi(L))$ in term of semialgebraic set (a more general
property than algebraic, which allows to cope with the fact that algebraic
sets are not closed w.r.t. the operation of product of sets). Afterwards, one
applies on the constructed formula the Tarski-Seidenberg quantifier
elimination to verify whether (2) holds true or not.

It turns out that the semialgebraicity of ${\mathbf{C}l}(\varphi(L))$, and its
effective computation (as a semialgebraic set), are reduced to those of an
algebro-combinatorial object that is associated with the grammar $G$
generating $L$, and with every variable $A$ of $G$: the monoid of cycles of
$A$. Such monoid, denoted $M_{A}$, corresponds (up to a technical detail) to
the matrix image, under taking the morphism $\varphi$ of (1), of the language
of cycles in $G$ associated with $A$ (see Eq. (21)).

The reduction process mentioned above is made possible by resorting to two
ingredients: the fact that the Euclidean closure ${\mathbf{C}l}(M_{A})$ is an
algebraic set (because of a deep result of Algebraic Geometry, namely Theorem
3) and because of a suitably defined effective structuring of the
computations, i.e., the derivations, of $G$ (Sections 4.1, 4.2 and 6.1). In
this theoretical setting, [7] and this work provides the following picture of
the Intersection Problem:

  * •

If $L$ is a context-free language, then ${\mathbf{C}l}(\varphi(L))$ is
semialgebraic. Moreover, if, for every variable $A$ of $G$,
${\mathbf{C}l}(M_{A})$ is effectively computable, then
${\mathbf{C}l}(\varphi(L))$ is so as well (Proposition 9).

  * •

If, for every variable $A$ of $G$, $M_{A}$ is finitely generated, then
${\mathbf{C}l}(\varphi(L))$ is effectively computable. This is guaranteed by
applying Proposition 9 and the results [12, 17, 25] mentioned above. This, in
particular, covers the cases of context-free linear languages, bounded semi-
linear languages and a new class of languages, proposed in this paper,
generated by restricted matrix context-free linear grammars which non
trivially extends the previous ones (Proposition 10).

  * •

The effective computation of ${\mathbf{C}l}(\varphi(L))$ is achieved for a
subfamily of finite index context-free languages, called monoidal, by
considering the property of (algebraic) irreducibility on the Zariski closure
of a family of monoids of cycles canonically associated with $G$ (Proposition
11).

The new results of the paper are the following. In Section 6.1, we extend the
main contribution of [7] – i.e., the statement of decidability of the
Intersection Problem for linear context-free languages and for bounded
semilinear languages – to a class of matrix context-free grammar of finite
index. Precisely, whenever the quantum automaton is rational, such result
(Proposition 10) allows, on one hand, to recover both the previous two cases
as immediate corollaries of such result. On the other, it shows the
decidability of the problem for languages of exponential growth that are not
context-free. The proof is based upon a combinatorial decomposition of these
matrix grammars proposed by Choffrut, Varricchio and the second author in [10]
for the study of rational relations. In particular, this decomposition permits
a refinement of the algebro-combinatorial machinery developed in [7] for the
manipulation of the monoids of cycles of these grammars.

In Section 6.2, we investigate the Intersection Problem for languages defined
by finite index context-free grammars. These are grammars $G$ where each word
$w$ in the language generated by $G$ is obtained by a derivation $\delta$,
whose index is uniformly bounded, i.e., the number of variables in each
sentential form of $\delta$ is bounded by an integer not depending on $w$. A
remarkable result by Ginsburg and Spanier [14] (see also Nivat [24]) provides
a charaterization of such languages in terms of composition of grammars:
precisely, each language of this type is generated by a grammar $G$ given by
the composition

$G={\cal G}_{1}\circ{\cal G}_{2}\circ\cdots\circ{\cal G}_{k},$ (3)

of families ${\cal G}_{i},\ 1\leq i\leq k,\ $ of linear context-free grammars.
Here, we prove a statement of decidability for a subclass of these grammars
called monoidal. Informally speaking, a grammar $G$ of the form (3) is
monoidal if the terminal productions of $G$ are of the form
$X\rightarrow\varepsilon$ and the remaining productions are unit ones or of
the form $X\rightarrow uXv$, with $X$ being a variable of some grammar of
${\cal G}_{i},\ 1\leq i\leq k$ (see Definition 10).

We prove that, whatever is the length $k$ of the composition (3) for $G$, if
the Zariski closure of the monoids of cycles of the linear grammars of the
lowest level ${\cal G}_{k}$ of (3), are (algebraic) irreducible, then one can
effectively computes the Euclidean closure ${\mathbf{C}l}(\varphi(L))$ of
$\varphi(L)$ (Proposition 11, Corollary 5).

Extensions of such result to broader families of finite index context-free
languages seem related to possible extensions of the algorithms [12, 17, 25]
(cf Section 7, [$\alpha$]).

The general case of context-free languages is still open and it would be even
possible that the problem is undecidable (cf Section 7, [$\beta$]).

The paper is structured in the following way. In Sec. 2 preliminaries on
semialgebraic and irreducible algebraic sets are presented. In Section 3 we
recall an effective condition to which the decidability of the problem under
discussion can be reduced. Section 4 provides combinatorial structurings of
context-free languages in the general case and in the finite index case.
Section 5 recalls some results relating context-free grammars and
semialgebraic sets. In Section 6 the main results of the paper are presented.
Section 7 contains some concluding remarks and open problems. Section 8 shows
the construction for monoidal grammars on an example.

##  2 Preliminaries on semialgebraic sets

Let us give first the definition of quantum automaton (cf. [6, 8, 23]).

###### Definition 1

A quantum automaton ${\cal Q}$ is a quadruple $(s,\varphi,P,\lambda)$ where
$s\in\mathbb{R}^{n}$ is a vector of unit norm, $P$ is a projection of
$\mathbb{R}^{n}$, i.e., $P\in\\{0,1\\}^{n\times n}$ with $P^{2}=P$, and
$\varphi$ is a morphism

$\varphi:\Sigma^{*}\longrightarrow O_{n},$ (4)

of the free monoid $\Sigma^{*}$ into the group $O_{n}$ of orthogonal $n\times
n$-matrices in $\mathbb{R}^{n\times n}$.

The behaviour of ${\cal Q}$ heavily depends on the topological properties of
the semigroup of matrices $\varphi(\Sigma^{*})$. This is why, before returning
to quantum automata, we first focus our attention on these matrices for their
own sake.

###  2.1 Topology

The following result is needed in the proof of the main theorem. It will be
applied in the particular case of orthogonal matrices. Given a subset $E$ of a
finite dimensional vector space, we denote by $\mathbf{C}l(E)$ the topological
closure for the topology induced by the Euclidean norm. Given a $k$-tuple of
matrices $(M_{1},\ldots,M_{k})$, denote by $f$ the $k$-ary product
$f(M_{1},\ldots,M_{k})=M_{1}\cdots M_{k}$ and extend the notation to subsets
${\cal A}$ of $k$-tuples of matrices by posing $f({\cal
A})=\\{f(M_{1},\ldots,M_{k})\mid(M_{1},\ldots,M_{k})\in{\cal A}\\}$. The
following result will be applied in several instances of this paper. It says
that because we are dealing with compact subsets, the two operators of matrix
multiplication and the topological closure commute.

###### Theorem 1

([7], Theorem 1) Let $\cal C$ be a compact subset of matrices and let ${\cal
A}\subseteq{\cal C}^{k}$ be a $k$-ary relation. Then we have
${\mathbf{C}l}(f({\cal A}))=f({\mathbf{C}l}({\cal A}))$.

Consequently, if ${\cal A}$ is a binary relation which is a direct product
${\cal A}_{1}\times{\cal A}_{2}$, we have ${\mathbf{C}l}({\cal A}_{1}{\cal
A}_{2})=f({\mathbf{C}l}({\cal A}_{1}\times{\cal A}_{2}))$. It is an elementary
result of topology that ${\mathbf{C}l}({\cal A}_{1}\times{\cal
A}_{2})={\mathbf{C}l}({\cal A}_{1})\times{\mathbf{C}l}({\cal A}_{2})$ holds.
Because of ${\mathbf{C}l}({\cal A}_{1}{\cal A}_{2})=f({\mathbf{C}l}({\cal
A}_{1}\times{\cal A}_{2}))=f({\mathbf{C}l}({\cal
A}_{1})\times{\mathbf{C}l}({\cal A}_{2}))={\mathbf{C}l}({\cal A}_{1})\
{\mathbf{C}l}({\cal A}_{2})$ we have

###### Corollary 1

The topological closure of the product of two sets of matrices included in a
compact subspace is equal to the product of the topological closures of the
two sets.

###  2.2 Algebraic and semialgebraic sets

Let us give first the definition of algebraic set over the field of real
numbers (cf. [3, 13, 26]).

###### Definition 2

A subset ${\cal A}\subseteq\mathbb{R}^{n}$ is algebraic (over the field of
real numbers), if ${\cal A}$ is the zero set of an arbitrary subset $\cal P$
of polynomials of $\mathbb{R}[x_{1},\ldots,x_{n}]$, i.e., for every vector
$v\in\mathbb{R}^{n}$,

$v\in{\cal A}\ \Longleftrightarrow\ \forall\ p\in{\cal P}:\ p(v)=0.$ (5)

The set ${\cal A}$ is said to be effective algebraic if the polynomials of
$\cal P$ can be computed by an effective procedure (algorithm).

Note that by the Hilbert basis Theorem, one may assume that the set $\cal P$
is finite. Even more, since we are dealing with algebraic sets over
$\mathbb{R}$, $\cal P$ can be reduced to a singleton since (5) can be assumed
to be to the equation

$\displaystyle\sum_{p\in\cal P}p(x)^{2}=0.$

One can check that the family of algebraic sets is closed under finite unions
and intersections. However, it is not closed under complement and projection.
The following more general class of subsets enjoys extra closure properties
and is therefore more robust.

###### Definition 3

A subset ${\cal A}\subseteq\mathbb{R}^{n}$ is semialgebraic (over the field of
real numbers) if it satisfies one of the two equivalent conditions

(i) ${\cal A}$ is the set of vectors satisfying a finite Boolean combination
of predicates of the form $p(x_{1},\ldots,x_{n})>0$ where
$p\in\mathbb{R}[x_{1},\ldots,x_{n}]$.

(ii) ${\cal A}$ is first-order definable in the theory of the structure whose
domain are the reals and whose predicates are of the form
$p(x_{1},\ldots,x_{n})>0$ and $p(x_{1},\ldots,x_{n})=0$ with
$p\in\mathbb{R}[x_{1},\ldots,x_{n}]$.

The set ${\cal A}$ is said to be effective semialgebraic if the formula
defining ${\cal A}$ can be effectively computed.

We now specify such definitions to square matrices.

###### Definition 4

A set ${\cal A}\subseteq\mathbb{R}^{n\times n}$ of matrices is algebraic
(resp., semialgebraic) if considered as a set of vectors of dimension $n^{2}$,
it is algebraic (resp., semialgebraic).

We now combine the notions of zero sets and of topology. In the following we
rephrase two results of [8] by emphasizing the main features that serve our
purpose. Given a subset $E$ of a group, we denote by $\langle E\rangle$ and by
$E^{*}$ the subgroup and the submonoid it generates, respectively.

###### Theorem 2

Let $S\subseteq\mathbb{R}^{n\times n}$ be a set of orthogonal matrices and let
$E$ be any subset of $S$ satisfying $\langle S\rangle=\langle E\rangle$. Then
we have ${\mathbf{C}l}(S^{*})={\mathbf{C}l}(\langle E\rangle)$. In particular
${\mathbf{C}l}(S^{*})$ is a group.

###### Proof.

It is known that every compact subsemigroup of a compact group is a subgroup
$G$. Now $S^{*}\subseteq\langle E\rangle$ implies
$G={\mathbf{C}l}(S^{*})\subseteq{\mathbf{C}l}(\langle E\rangle)$ and
$S\subseteq G$ implies ${\mathbf{C}l}(\langle E\rangle)\subseteq G$ and thus
${\mathbf{C}l}(S^{*})={\mathbf{C}l}(\langle E\rangle)$. ∎∎

The main consequence of the next theorem is that the topological closure of a
monoid of orthogonal matrices is algebraic ([26], Ch. 3, Sec. 4, Theorem $5$).

###### Theorem 3

Let $E$ be a set of orthogonal matrices. Then ${\mathbf{C}l}(\langle
E\rangle)$ is a subgroup of orthogonal matrices and it is the zero set of all
polynomials $p[x_{1,1},\ldots,x_{n,n}]$ satisfying the conditions

$p(I)=0\ \mbox{ and }p(eX)=p(X)\ \mbox{ for all }e\in E$

Furthermore, if the matrices in $E$ have rational coefficients, the above
condition may be restricted to polynomials with coefficients in $\mathbb{Q}$.

###  2.3 Closure properties of semialgebraic sets

The _product_ of two sets of matrices is defined as

${\cal A}_{1}{\cal A}_{2}=\\{M_{1}M_{2}\mid M_{1}\in{\cal A}_{1},M_{2}\in{\cal
A}_{2}\\}.$ (6)

We define the _sandwich_ operation denoted by $\diamond$ whose first operand
is a set of pairs of matrices ${\cal A}\subseteq\mathbb{R}^{n\times
n}\times\mathbb{R}^{n\times n}$ and the second operand a set of matrices
${\cal B}\subseteq\mathbb{R}^{n\times n}$ by setting

${\cal A}\diamond{\cal B}=\\{XYZ\mid(X,Z)\in{\cal A}\mbox{ and }Y\in{\cal
B}\\}$

The next operation will be used. Given a bijection

$\pi:\\{(i,j)\mid i,j\in\\{1,\ldots,n\\}\\}\rightarrow\\{(i,j)\mid
i,j\in\\{1,\ldots,n\\}\\}$ (7)

and a matrix $M\in\mathbb{R}^{n\times n}$ denote by $\pi(M)$ the matrix
$\pi(M)_{i,j}=M_{\pi(i,j)}$. Extend this operation to subsets of matrices
${\cal A}$. Write $\pi({\cal A})$ to denote the set of matrices $\pi(M)$ for
all $M\in{\cal A}$.
The last operation is the _sum_ of square matrices $M_{1},\ldots,M_{k}$ whose
result is the square block matrix

$M_{1}\oplus\cdots\oplus M_{k}=\left(\begin{array}[]{cccc}M_{1}&0&\cdots&0\\\
0&M_{2}&\cdots&0\\\ \vdots&\vdots&\vdots&\vdots\\\
0&0&0&M_{k}\end{array}\right)$ (8)

These notations extend to subsets of matrices in the natural way. Here we
assume that all $k$ matrices have the same size $n\times n$. Observe that if
the matrices are orthogonal, so is their sum. Such matrices form a subgroup of
orthogonal matrices of size $kn\times kn$.

Now we recall some closure properties of the class of effective semialgebraic
matrices investigated in [7]. Let us first consider the operation (6). We
adopt the following conventions: we write $\exists^{n}X$ to mean that $X$ is a
vector of $n$ bound variables. Furthermore, a vector of $n\times n$ variables
can be interpreted as an $n\times n$ matrix of variables. Consider two
semialgebraic sets of matrices, say ${\cal A}_{1}$ and ${\cal A}_{2}$,
respectively defined by first-order formulas $\Phi_{1}(X_{1})$ and
$\Phi_{2}(X_{2})$ where $X_{1}$ and $X_{2}$ are two families of $n^{2}$ free
variables viewed as two $n\times n$ matrices of variables. Then ${\cal
A}_{1}{\cal A}_{2}$ is defined by the following formula where $X$ is a family
of $n^{2}$ free variables viewed as an $n\times n$ matrix

$\exists^{n\times n}X_{1}\;\exists^{n\times
n}X_{2}:X=X_{1}X_{2}\wedge\Phi_{1}(X_{1})\wedge\Phi_{2}(X_{2})$

and $X=X_{1}X_{2}$ is an abbreviation for the predicate defining $X$. This
shows that the class of effective semialgebraic sets of matrices is closed
with respect to (6). The verification of the properties stated below is done
similarly.

###### Proposition 1

Let ${\cal A}_{1},{\cal A}_{2}\subseteq\mathbb{R}^{n\times n}$ be two sets of
matrices, and let $\pi$ be a one-to-one mapping as in (7).

1) If ${\cal A}_{1}$ and ${\cal A}_{2}$ are algebraic (resp., effective
algebraic) so are ${\cal A}_{1}\cup{\cal A}_{2},{\cal A}_{1}\cap{\cal A}_{2}$,
and $\pi({\cal A}_{1})$.

2) If ${\cal A}_{1}$ and ${\cal A}_{2}$ are semialgebraic (resp., effective
semialgebraic), so are ${\cal A}_{1}\cup{\cal A}_{2}$, ${\cal A}_{1}{\cal
A}_{2}$ and $\pi({\cal A}_{1})$.

###### Proposition 2

Let ${\cal A}_{1}\subseteq\mathbb{R}^{n\times n}\times\mathbb{R}^{n\times n}$
and ${\cal A}_{2}\subseteq\mathbb{R}^{n\times n}$ be semialgebraic (resp.,
effective semialgebraic). Then ${\cal A}_{1}\diamond{\cal A}_{2}$ is are
semialgebraic (resp., effective semialgebraic).

###### Proposition 3

Let ${\cal A}$ be a semialgebraic (resp., effective semialgebraic) set of
$kn\times kn$ matrices of the form (8). The set $\\{X_{1}\cdots X_{k}\mid
X_{1}\oplus\cdots\oplus X_{k}\in{\cal A}\\}$ is semialgebraic (resp.,
effective semialgebraic).

###### Proposition 4

If ${\cal A}_{1},\ldots,{\cal A}_{k}\subseteq\mathbb{R}^{n\times n}$ are
algebraic (resp., effective algebraic, semialgebraic, effective
semialgebraic), then so is the set ${\cal A}_{1}\oplus\cdots\oplus{\cal
A}_{k}$.

###  2.4 Algebraic Irreducible sets

Let us consider the topological space obtained by equipping $\mathbb{R}^{m}$
with the Zariski topology. Given a non-empty subset $\cal Z$ of
$\mathbb{R}^{m}$, $\cal Z$ is said to be irreducible if $\cal Z$ cannot be
written as the union of two closed, i.e. algebraic, subsets of $\cal Z$,
distinct from $\emptyset$ and $\cal Z$ itself. It can be proven that a non-
empty algebraic subset $\cal Z$ of $\mathbb{R}^{m}$ is irreducible if and only
if its vanishing ideal is a prime ideal (cf [13], Prop. 1.1.12). Irreducible
sets will play a role in this theoretical setting (cf Sec. 6.2). To this
purpose, we recall some basic results. The next notation is useful.

Notation. The Zariski closure of a set $\cal A$ will be denoted by
$\overline{\cal A}$.

###### Definition 5

Given non-empty algebraic sets ${\cal V}\subseteq\mathbb{R}^{n}$ and ${\cal
W}\subseteq\mathbb{R}^{m}$, a map $f:{\cal V}\rightarrow~{}{\cal W}$ is said
to be regular444 By following a well-established vocabulary in Automata
Theory, the term regular will be also used in Sec. 4 to name the family of
subsets of monoids defined by finite automata (or a morphism of algebraic
sets), if there exist $p_{1},\dots,p_{m}\in\mathbb{R}[x_{1},.\ldots,x_{n}]$
(where the $x_{i}$ are indeterminates) such that, for all ${\bf
x}=(x_{1},\ldots,n_{n})$ in $\cal V$

$f({\bf x})=(p_{1}({\bf x}),\dots,p_{m}({\bf x})).$ (9)

The following fact is well known (cf [13], Remark 1.3.2).

###### Lemma 1

If $f:{\cal V}\rightarrow{\cal W}$ is a regular map and $\cal V$ is
irreducible, then the Zariski closure $\overline{f({\cal V})}$ of ${f({\cal
V})}$ is also irreducible.

We will now consider irreducible algebraic sets of the group
GL${}_{m}(\mathbb{R})$ of invertible $m\times m$ matrices over $\mathbb{R}$
equipped with the Zariski topology. The next closure properties can be readily
checked.

###### Proposition 5

The family of irreducible algebraic sets is closed with respect to the
operations (7), (8) and the (finite) Cartesian product of sets.

###### Proof.

Let $\cal A$ be an irreducible algebraic set. By Proposition 1, with $\pi$ as
in (7), $\pi({\cal A})$ is algebraic so $\overline{(\pi({\cal A}))}=\pi({\cal
A})$ and the claim comes from Lemma 1 since $\pi$ is a regular map. For the
operation (8) and Cartesian product, the fact that, given irreducible
algebraic sets ${\cal A}_{1},\ldots,{\cal A}_{k}$, then so is the set ${\cal
A}_{1}\oplus\cdots\oplus{\cal A}_{k}$ (resp., ${\cal
A}_{1}\times\cdots\times{\cal A}_{k}$) comes from [13], Prop. 1.3.8-(a).∎∎

The proof of the next lemma is almost immediate.

###### Lemma 2

Let $H_{1},\ldots,H_{m}$ be subsets of an arbitrary monoid M, every one of
which contains the identity $1$ of M. Then $(H_{1}\cup\ldots\cup
H_{m})^{*}=(H_{1}\cdots H_{m})^{*}$.

###### Proof.

We prove the claim for $m=2$, i.e., $(A\cup B)^{*}=(AB)^{*}$ since the general
case is treated similarly. The inclusion $(A\cup B)^{*}\supseteq(AB)^{*}$ is
obvious. For the reverse inclusion, assume $m=m_{1}\dots m_{\ell},\ m_{i}\in
A\cup B,\ 1\leq i\leq\ell$. Then $m$ can be written as $m=a_{1}b_{1}\cdots
a_{\ell}b_{\ell}$, where, for every $i=1,\ldots,\ell$ $a_{i}=m_{i}$ and
$b_{i}=1$ if $m_{i}\in A$ while $a_{i}=1$ and $b_{i}=m_{i}$ if $m_{i}\in B$.
∎∎

We now introduce an useful notation.

Notation. Given a subset $\cal A$ of the group $O_{m}$ of orthogonal matrices
(over $\mathbb{R}$) of order $m\geq 1$, we write ${\cal A}\in({\cal H})$ if

${\cal A}=\bigcup_{i=1}^{k}{\cal A}_{i},$ (10)

where, for every $i=1,\ldots,k$, ${\cal A}_{i}$ is an irreducible, effective
algebraic set that contains the identity matrix $I$.

###### Proposition 6

Let $\cal A$ be a subset of $O_{nk}$ with ${\cal A}\in({\cal H})$ and let
$\Psi$ be a regular map

$\Psi:O_{nk}\;\;\displaystyle\mathop{\longrightarrow}\;\;O_{n}.$

If, for every $i=1,\ldots,k$, $\Psi({\cal A}_{i})$ contains $I$, then
$\overline{\Psi({\cal A})^{*}}\in({\cal H})$. In particular $\Psi({\cal A)}$
is effective algebraic.

###### Proof.

Let ${\cal A}=\bigcup_{i=1}^{k}{\cal A}_{i}$ be a set as in (10). We may
suppose that $k=2$, i.e. ${\cal A}={\cal A}_{1}\cup{\cal A}_{2}$, since the
general case can be treated similarly. Hence $\Psi({\cal A})=\Psi({\cal
A}_{1}\cup{\cal A}_{2})$ so, by Lemma 2,

$\Psi({\cal A})^{*}=(\Psi({\cal A}_{1})\Psi({\cal A}_{2}))^{*}.$

Let $H_{1}=\overline{\Psi({\cal A}_{1})\Psi({\cal A}_{2})}$. By Lemma 1,
$\overline{\Psi({\cal A}_{i})}$ $(i=1,2),$ is an algebraic irreducible set.
Further, by hypothesis, $\overline{\Psi({\cal A}_{i})}$ contains $I$.
Following [12], Sec. 3.1, by using Gröbner bases techniques, since ${\cal
A}_{i}$ is effective algebraic and $\Psi$ is a regular map, then one can
effectively compute $\overline{\Psi({\cal A}_{i})}$.

Now we observe that

$\overline{\overline{{\Psi(\cal A}_{1})}\cdot\overline{\Psi({\cal A}_{2}})}\
=\ \overline{\Psi({\cal A}_{1})\cdot\Psi({\cal A}_{2})}.$ (11)

Indeed, taking the map m$:O_{n}\times O_{n}\rightarrow O_{n}$ defined, for
every $X,Y\in O_{n}$, as m$(X,Y):=X\cdot Y$, one has that m is a regular and
thus continuous map (w.r.t. $O_{n}$ endowed with the Zariski topology and
$O_{n}\times O_{n}$ with the induced product topology). This implies, for
arbitrary sets ${\cal X}_{1},{\cal X}_{2},$ that
$\overline{\mbox{m}(\overline{{\cal X}_{1}},\overline{{\cal
X}_{2}})}=\overline{\mbox{m}({\cal X}_{1},{\cal X}_{2})},$ and thus (11).

Let $H_{2}=\overline{H_{1}\cdot H_{1}}$. Since $I\in H_{1}$ then one has $I\in
H_{2}$. By the very same argument used for $H_{1}$ one has that $H_{2}$ is an
irreducible effective algebraic set such that $H_{2}=\overline{\Psi({\cal
A})^{2}}$.

Finally, let us define recursively the family of sets of $O_{n}$

$\\{H_{i}\\}_{i\geq 1},$

where $H_{0}=\\{I\\}$ and, for every $i\geq 1$,

$H_{i}=\overline{H_{i-1}\cdot H_{1}}.$

By proceeding as in the previous cases, one has that, for every $i\geq 3$,
$H_{i}$ is an effective algebraic irreducible set such that
$H_{i}=\overline{(\Psi({\cal A}_{1})\Psi({\cal A}_{2}))^{i}}$. and containing
$I$. Moreover, since, for each $i\geq 1$, $I\in H_{i}$, then one has the
following ascending chain

$H_{1}\;\subseteq\;H_{2}\;\subseteq\;\cdots\;H_{i}\;\subseteq\;\cdots$ (12)

which, by the irreducibility of all of its terms, terminates, i.e., there
exists some $m\in\mathbb{N}$ such that (cf Remark 1)

$H_{m+1}\ =\ \overline{(\Psi({\cal A}_{1})\Psi({\cal A}_{2}))^{m\ +\ 1}}\ =\
\overline{(\Psi({\cal A}_{1})\Psi({\cal A}_{2}))^{m}}\ =\ H_{m}.$ (13)

Finally let ${\cal X}=\bigcup_{i\geq 1}\ H_{i}$. By (13), $\overline{\cal
X}=H_{1}\cup\cdots\cup H_{m}$. On the other hand, since, for every $i\geq 1$,
$H_{i}=\overline{(\Psi({\cal A}_{1})\Psi({\cal A}_{2}))^{i}}$, then it is
readily checked that

$\overline{\cal X}=H_{1}\cup\cdots\cup H_{m}=\overline{\Psi({\cal A})^{*}}.$

This proves the claim. ∎∎

###### Remark 1

Observe that the integer $m$ of (13) can be bounded. Indeed, recall that, by
[13], Proposition 1.2.20 , if ${\cal V},{\cal W}\subseteq\mathbb{R}^{m}$ are
algebraic sets and ${\cal V}$ is irreducible, then dim$({\cal V})<$dim$({\cal
W})$, if ${\cal V}\subset{\cal W}$. Since all the sets of (12) are irreducible
algebraic subset of GL${}_{n}(\mathbb{R})$, which has dimension $n^{2}$, one
has $m\leq n^{2}$.

##  3 Effectiveness issues

We now return to the $(L,{\cal Q})$ Intersection problem as defined in the
Introduction. The main bulk of this decidability result is based upon the
following proposition that is obtained by proceeding as in [8]. For the sake
of completeness, we recall the proof.

###### Proposition 7

([7], Proposition 1) Let ${\cal Q}$ be a rational quantum automaton. Let
$L\subseteq\Sigma^{*}$ be a formal language such that the set
${\mathbf{C}l}(\varphi(L))$ is effective semialgebraic. It is recursively
decidable whether or not $L\cap|{\cal Q}_{>}|=\emptyset$ holds.

###### Proof.

Equivalently we prove the inclusion $L\subseteq|{\cal Q}_{\leq}|$. We run in
parallel two semialgorithms. The first one verifies the noninclusion by
enumerating the words $w\in L$ and testing if $||s\varphi(w)P||>\lambda$
holds. The second semialgorithm considers an effectively computable polynomial
$\phi(X)$ which defines ${\mathbf{C}l}(\varphi(L))$ and verifies whether the
sentence

$\Psi\ \equiv\ \forall X:\phi(X)\Rightarrow sXP\leq\lambda$

holds, which can be achieved by Tarski Seidenberg elimination result. If the
inclusion $L\subseteq|{\cal Q}_{\leq}|$ holds then the first semialgorithm
cannot answer “yes” and the second semialgorithm will answer “yes”. Now assume
that the inclusion does not hold. Then the first semialgorithm will eventually
answer “yes”, while the second semialgorithm cannot answer “yes” since this
would imply that $\Psi$ holds and thus

$\forall X:X\in{\mathbf{C}l}(\varphi(L))\Rightarrow||sXP||\leq\lambda,$

a contradiction. ∎∎

Proposition 7 shows that the decidability of the problem relies upon the
computation of ${\mathbf{C}l}(\varphi(L))$. In the sequel, we will investigate
the case of context-free languages. In order to deal with this case, we will
use two main tools: first, an algorithm by Derksen et al. [12], already
mentioned in the Introduction, that computes the Zariski closure of a finitely
generated group of matrices over a field; secondly, a suitable combinatorial
structuring of a context-free language based upon some special structures
named cycles. The last will be presented in the next section.

##  4 Preliminaries on context-free languages

For the sake of self-containment and in order to fix notation, we just recall
few essential terms of context-free languages and regular sets of monoids,
that can be found in all introductory textbooks on theoretical computer
science (see, for instance, [4, 15, 16]).

Given a monoid $M,$ a subset of $M$ is said to be regular if it is finite or
it is obtained from finite sets by using finitely many times the regular
operations, i.e., the union of two sets, the product $(\cdot)$ of two sets,
and the star $(^{*})$, this last operation associating with a set $\cal X$ the
submonoid ${\cal X}^{*}$ generated by $\cal X$. It is worth noticing that the
concept of regular set can be equivalently given in terms of $M$-automaton. We
will recall this equivalence in the appropriate points (cf Lemma 6,
Proposition 10).

A _context-free grammar_ $G$ is a quadruple $\langle V,\Sigma,P,S\rangle$
where $\Sigma$ is the alphabet of _terminal symbols_ , $V$ is the set of
_variables_ or _nonterminal symbols_ , $P$ is the set of _rules_ or
_productions_ , and $S$ is the _axiom_ of the grammar. A word over the
alphabet $\Sigma$ is called terminal. As usual, the nonterminal symbols are
denoted by uppercase letters as, for instance, $A$, $B$. An arbitrary rule of
the grammar is written as $A\rightarrow\alpha$. The _derivation_ relation of
$G$ is denoted by $\displaystyle\mathop{\Rightarrow}^{*}$. The language
generated by $G$ is the subset of terminal words
$\\{w\in\Sigma^{*}:S\displaystyle\mathop{\Rightarrow}^{*}w\\}$ denoted by
$L(G)$.

The family of context-free languages will be denoted by CFL.

Following [4], Sec. VII.5, we say that a context-free language $L$ is of index
$k$, if there exist a context-free grammar $G$ with $L=L(G)$ and an integer
$k\in\mathbb{N}$ such that the following property holds: for every word $w\in
L(G)$, there exists a derivation
$\delta=(S\displaystyle\mathop{\Rightarrow}^{*}w)$ such that the number of
occurrences of variables in each sentential form of $\delta$ does not exceed
$k$. The family of context-free languages of index $k$ will be denoted by
$Ind(k)$ and ${\cal L}(IND_{FIN})$ will denote the family of all the languages
of finite index, that is, $\bigcup_{k\in\mathbb{N}}Ind(k)$. One immediately
sees that the most simple languages in such a family are those of $LIN$, the
linear languages, i.e. those generated by grammars where the right hand side
$\alpha$ of every rule $A\rightarrow\alpha$, contains at most one occurrence
of nonterminal symbols, that is,
$\alpha\in\Sigma^{*}\cup\Sigma^{*}V\Sigma^{*}$. A well-known result proven by
Salomaa in [29] shows that Dyck languages cannot be generated by finite index
grammars, thus implying ${\cal L}(IND_{FIN})\subset\ $CFL. The importance of
the family ${\cal L}(IND_{FIN})$ is due to the fact that, by a well-known
result by Baron and Kuich [2] (up to a technical restriction) the unambiguous
context-free languages whose characteristic series in commutative variables
are rational, are exactly those in ${\cal L}(IND_{FIN})$. For this reason,
such languages are also called “quasi-rational” (see Section 4.2).

###  4.1 Structuring of CFL

We now find convenient to recall a combinatorial structuring of an arbitrary
context-free language (see [7], Sec. 3). Such decomposition follows a
recursive scheme proposed by Incitti in [20] based upon the concept defined
below.

###### Definition 6

With each nonterminal symbol $A\in V$ associate the subset of
$\Sigma^{*}\times\Sigma^{*}$ defined as

$C_{A}=\\{(\alpha,\beta)\in\Sigma^{*}\times\Sigma^{*}:A\displaystyle\mathop{\Rightarrow}^{*}\alpha
A\beta\\}.$

$C_{A}$ will be called the set of cycles of $A$. 555According to the
terminology of [15], a cycle is a derivation of the form
$A\displaystyle\mathop{\Rightarrow}^{*}\alpha A\beta$. With a minor abuse of
language, we will call cycle the pair of contexts $(\alpha,\beta)$ also

It is convenient to define the sandwich operation (cf Sec. 2.3) also for
languages in the following way. If $C_{A}$ is the set above and $L^{\prime}$
an arbitrary language, we define the subset of $\Sigma^{*}$

$C_{A}\diamond L^{\prime}=\\{uwv\mid(u,v)\in{C_{A}}\mbox{ and
}w\in{L^{\prime}}\\}$

As the proof of the main theorem proceeds by induction on the number of
nonterminal symbols, we need to show how to recombine a grammar from simpler
ones obtained by choosing an arbitrary non-axiom symbol as the new axiom and
by canceling all the rules involving $S$. This is the reason for introducing
the next notation.

###### Definition 7

Let $G=\langle V,\Sigma,P,S\rangle$ be a context-free grammar. Set
$V^{\prime}=V\setminus\\{S\\}$.

For every $A\in V^{\prime}$, define the context-free grammar $G_{A}=\langle
V^{\prime},\Sigma,P_{A},A\rangle$ where the set $P_{A}$ consists of all the
rules $B\rightarrow\gamma$ of $G$ of the form

$\quad B\in V^{\prime},\quad\gamma\in(V^{\prime}\cup\Sigma)^{*}$

and denote by $L_{A}$ the language of all terminal words generated by the
grammar $G_{A}$.

The next definition introduces the language of terminal words obtained in a
derivation where $S$ occurs at the start only.

###### Definition 8

Let $L^{\prime}(G)$ denote the set of all the words of $\Sigma^{*}$ which
admit a derivation

$S\Rightarrow\gamma_{1}\Rightarrow\cdots\Rightarrow\gamma_{\ell}\Rightarrow w$
(14)

where, for every $i=1,\ldots,\ell$, $\gamma_{i}\in(V^{\prime}\cup\Sigma)^{*}$.

The language $L^{\prime}(G)$ can be easily expressed in terms of the languages
$L_{A}$ for all $A\in V^{\prime}$. Indeed, consider the set of all rules of
the grammar $G$ of the form

$S\rightarrow\beta,\quad\beta\in(V^{\prime}\cup\Sigma)^{*}$ (15)

Factorize every such $\beta$ as

$\beta=w_{1}A_{1}w_{2}A_{2}\cdots w_{\ell}A_{\ell}w_{j_{\ell+1}}$ (16)

where $w_{1},\ldots,w_{\ell+1}\in\Sigma^{*}$ and $A_{1},A_{2},\ldots
A_{\ell}\in V^{\prime}$. Next lemma easily follows from the previous
definitions.

###### Lemma 3

With the notation of (16), the language $L^{\prime}(G)$ is the finite union of
the languages

$w_{1}L_{A_{1}}w_{2}L_{A_{2}}\cdots w_{\ell}L_{A_{\ell}}w_{j_{\ell+1}}$

when $\beta$ ranges over all rules (15).

###### Proposition 8

With the previous notation $L$ is a finite union of languages of the form
$C_{S}\diamond L^{\prime\prime}$ where

$L^{\prime\prime}=w_{1}L_{A_{1}}w_{2}L_{A_{2}}\cdots
w_{\ell}L_{A_{\ell}}w_{\ell+1}$

###### Proof.

In order to prove the inclusion of the right- into left- hand side, it
suffices to consider $w=\alpha u\beta,$ with $u\in L^{\prime}(G)$ and
$(\alpha,\beta)\in C_{S}.$ One has $S\displaystyle\mathop{\Rightarrow}^{*}u$
and $S\displaystyle\mathop{\Rightarrow}^{*}\alpha S\beta$ so that
$S\displaystyle\mathop{\Rightarrow}^{*}\alpha
S\beta\mathop{\Rightarrow}^{*}\alpha u\beta,$ and thus $w\in L$.

Let us prove the opposite inclusion. A word $w\in L$ admits a derivation
$S\displaystyle\mathop{\Rightarrow}^{*}w$. If the symbol $S$ does not occur in
the derivation except at the start of the derivation, then $w\in
L^{\prime}(G)$. Otherwise factor this derivation into
$S\displaystyle\mathop{\Rightarrow}^{*}\alpha S\beta\mathop{\Rightarrow}^{*}w$
such that $S$ does not occur in the second part of the derivation except in
the sentential form $\alpha S\beta$. Reorder the derivation
$\displaystyle\alpha S\beta\mathop{\Rightarrow}^{*}w$ into
$\displaystyle\alpha S\beta\mathop{\Rightarrow}^{*}\gamma
S\delta\mathop{\Rightarrow}^{*}w$ so that $\gamma,\delta\in\Sigma^{*}$. This
implies $w=\gamma u\delta$ for some $u\in L^{\prime}(G)$, which, by Lemma 3,
completes the proof. ∎∎

###  4.2 Structuring of ${\cal L}(IND_{FIN})$

We now recall a characterization, by Ginsburg and Spanier [14] (see also Nivat
[24]), of languages of ${\cal L}(IND_{FIN})$, that will be used in Section
6.2. To this purpose, we first recall that, given alphabets $\Sigma_{1}$ and
$\Sigma_{2}$, and a family $\cal F$ of languages of $\Sigma_{2}^{*}$, a $\cal
F$-substitution is a morphism
$\theta:\Sigma_{1}^{*}\rightarrow\Pi(\Sigma_{2}^{*})$ from the free monoid
$\Sigma_{1}^{*}$ into the multiplicative monoid $\Pi(\Sigma_{2}^{*})$ of
subsets of the free monoid $\Sigma_{2}^{*}$ such that

$\forall\ x\in\Sigma_{1}\quad\theta(x)\in\cal F.$

Let us define, recursively, the family $\\{Qrt(k)\\}_{k\in\mathbb{N}}\ $ of
quasi-rational languages of rank $k$ (or bounded derivation languages of rank
$k$) as:

$Qrt(k)=\left\\{\begin{array}[]{ll}LIN&\quad\mbox{if}\ k=1,\\\ LIN\circ
Qrt(k-1)&\quad\mbox{if}\ k>1,\end{array}\right.$ (17)

where $LIN\circ Qrt(k-1)$ denotes the family of all the languages obtained as
the images of linear languages, via $Qrt(k-1)$-substitutions, $\ k>1$, i.e.

$\\{\theta(L):L\in LIN,\,\quad\forall\;x\in\Sigma_{1}\;\;\;\theta(x)\in
Qrt(k-1)\\}.$

The following holds ([14], Theorem 4.2, cf also [4], Sec. VII.5, Theorem 5.2).

###### Theorem 4

For every $k\geq 1$, $Ind(k)=Qrt(k).$

####  4.2.1 Composition of grammars

For our next use, we will now describe how quasi-rational languages can be
characterized in terms of composition of grammars.

For this purpose, we recall the construction of the grammar that generates the
image $\theta(L)$ of a context-free language $L$ over the alphabet
$\Sigma_{1}$ under a context-free substitution
$\theta:\Sigma_{1}^{*}\rightarrow\Pi(\Sigma_{2}^{*})$, i.e. a $\cal
F$-substitution, with $\cal F$=CFL.

We follow verbatim the argument of [4], Sec. II.2. Let ${\cal G}_{1}=\langle
V_{1},\Sigma_{1},P_{1},S\rangle$ be the grammar that generates $L$ and let

${\cal G}_{2}=\\{G_{x}\ :\ x\in\Sigma_{1}\\}$

be the family of grammars where, for every $x\in\Sigma_{1}$,

$G_{x}=\langle V_{x},\Sigma_{2},P_{x},S_{x}\rangle$

is the grammar that generates $\theta(x)$. One may assume that $V_{1}\cap
V_{x}=\emptyset$, for all $x\in\Sigma_{1}$. Let be the set

${\cal V}_{2}=\\{S_{x}:x\in\Sigma_{1}\\}$

and let the copy morphism

$\mbox{c}:(V_{1}\cup\Sigma_{1})^{*}\rightarrow(V_{1}\cup{\cal V}_{2})^{*},$
(18)

defined as: $\mbox{c}(z)=z$, if $z\in V_{1}$, and $\mbox{c}(z)=S_{z}$, if
$z\in\Sigma_{1}$. With respect to c, consider the grammar $G_{\mbox{c}}$ that
generates $\mbox{c}(L)$. Such a grammar is defined as

$G_{\mbox{c}}=\langle V_{1},\\{S_{x}:x\in\Sigma_{1}\\},P_{\mbox{c}},S\rangle,$

where $P_{\mbox{c}}=\\{A\rightarrow\mbox{c}(\alpha):(A\rightarrow\alpha)\in
P\\}$. Finally, define

$H=\langle W,\Sigma_{2},Q,S\rangle$ (19)

as the grammar where

$W=V_{1}\ \cup\ \bigcup_{x\in\Sigma_{1}}\ V_{x},\quad\quad Q=P_{\mbox{c}}\
\cup\ \bigcup_{x\in\Sigma_{1}}\ P_{x}.$

The grammar $H$ so obtained will be called the composition of ${\cal G}_{1}$
and ${\cal G}_{2}$ and denoted by

$G={\cal G}_{1}\circ{\cal G}_{2}.$ (20)

###### Remark 2

By a minor abuse of notation, up to the copy morphism (18), one may identify
$\Sigma_{1}$ with ${\cal V}_{2}$. In particular ${V}_{1}\cap{\cal
V}_{2}=\emptyset.$

The following lemma holds.

###### Lemma 4

$\theta(L)=L({\cal G})$.

A composition of $k$ families of grammars $({\cal G}_{1},\ldots,{\cal
G}_{k}),$ with $k\geq 1$ will be the grammar

$G={\cal G}_{1}\circ{\cal G}_{2}\circ\cdots\circ{\cal G}_{k},$

obtained by iterating $(k-1)$ times the operation (20) of composition of
grammars on the families of context-free grammars ${\cal G}_{1},\ldots,{\cal
G}_{k}$ (if the operation is well defined). By (17), Theorem 4 can be
formulated as follows.

###### Theorem 5

Let $L$ be an arbitrary language of $Qrt(k),\ k\geq 1$. Then $L$ is generated
by a composition of $k$ families of linear grammars.

###### Example 1

Let $\cal L$ be the language over $\Sigma_{2}=\\{a,b\\}$ given by

${\cal L}=\\{a^{n}b^{n}:n\in\mathbb{N}\\}^{*}.$

Observe that $\cal L$ is the image of the language
$\\{x^{n}:n\in\mathbb{N}\\}$, $\Sigma_{1}=\\{x\\}$, under the substitution
$\theta:\Sigma_{1}^{*}\rightarrow\Pi(\Sigma_{2}^{*})$, with
$\theta(x)=\\{a^{n}b^{n}:n\in\mathbb{N}\\}$. Hence $\cal L$ is context-free of
index $2$. Then $\cal L$ is generated by the composition $G={\cal
G}_{1}\circ{\cal G}_{2}$ of the linear grammars ${\cal G}_{1}=\langle
V_{1},\Sigma_{1},P_{1},S\rangle$ and ${\cal G}_{2}=\langle
V_{2},\Sigma_{2},P_{2},\sigma\rangle$ where

$V_{1}=\\{S\\},\;\Sigma_{1}=\\{\sigma\\},\;P_{1}=\\{S\rightarrow\varepsilon,\;S\rightarrow\sigma
S\\},$

and

$V_{2}=\\{\sigma\\},\;\Sigma_{2}=\\{a,b\\},\;P_{2}=\\{\sigma\rightarrow\varepsilon,\;\sigma\rightarrow
a\sigma b\\}.$

##  5 Context-free languages and semialgebraic sets

Now we find convenient to recall (fixing some details of the proof) a property
(cf [7], Prop. 7), obtained from the decomposition of Section 4.1. This
property is relevant in this study since it states, for an arbitrary context-
free language $L$, that the closure ${\mathbf{C}l}(\varphi(L))$ of the image
of $L$, under the morphism (4) associated with a quantum automaton, is
semialgebraic. To this purpose, the following construction is crucial. With an
arbitrary nonterminal $A$ of $G$, associate the set $M_{A}$ defined as

$M_{A}=\\{\varphi(u_{1})\oplus\varphi(u_{2})^{\mbox{T}}\mid(u_{1},u_{2})\in
C_{A}\\},$ (21)

where $\varphi(u_{2})^{\mbox{T}}$ denotes the transpose of $\varphi(u_{2})$.
$M_{A}$ will be called the monoid of cycles of $A$ since the following holds.

###### Lemma 5

Let $A$ be a nonterminal symbol of $G$. $M_{A}$ is a monoid and its closure
${\mathbf{C}l}(M_{A})$ is an algebraic group.

###### Proof.

Observe first that $M_{A}$ is a subsemigroup of the group $O_{n}\oplus O_{n}.$
Indeed, if $\varphi(u_{1})\oplus\varphi(u_{2})^{\mbox{T}}$ and
$\varphi(v_{1})\oplus\varphi(v_{2})^{\mbox{T}}$ are in $M_{A}$ then we have

$(\varphi(u_{1})\oplus\varphi(u_{2})^{\mbox{T}})(\varphi(v_{1})\oplus\varphi(v_{2})^{\mbox{T}})=\varphi(u_{1}v_{1})\oplus\varphi(u_{2})^{\mbox{T}}\varphi(v_{2})^{\mbox{T}},$
(22)

where $(u_{1},u_{2}),(v_{1},v_{2})\in C_{A}$. On the other hand,
$(u_{1}v_{1},v_{2}u_{2})\in C_{A}$ and the corresponding matrix of $M_{A}$

$\varphi(u_{1}v_{1})\oplus\varphi(v_{2}u_{2})^{\mbox{T}}$ (23)

equals (22) for
$\varphi(v_{2}u_{2})^{\mbox{T}}=\varphi(u_{2})^{\mbox{T}}\varphi(v_{2})^{\mbox{T}}.$
Since $(\varepsilon,\varepsilon)\in M_{A}$, then $M_{A}$ is a monoid. The
second statement comes from Theorems 2 and 3. ∎∎

###### Proposition 9

Let $L$ be a context-free language. The set ${\mathbf{C}l}(\varphi(L))$ is
semialgebraic. Moreover, if for every $A\in V$, ${\mathbf{C}l}(M_{A})$ is
effective algebraic, then ${\mathbf{C}l}(\varphi(L))$ is effective
semialgebraic.

###### Proof.

By Proposition 8, the language $L$ is a finite union of languages of the form
$C_{S}\diamond L^{\prime\prime}$ with

$L^{\prime\prime}=w_{1}L_{A_{1}}w_{2}L_{A_{2}}\cdots
w_{\ell}L_{A_{\ell}}w_{\ell+1}$ (24)

where, for every $1\leq i\leq\ell+1$, $w_{i}\in\Sigma^{*}$ and $A_{i}\in
V^{\prime}$. It suffices to show by induction on the number of nonterminal
symbols that the subsets

${\mathbf{C}l}(\varphi(C_{S})\diamond\varphi(L^{\prime\prime}))$ (25)

are algebraic. If $\mathop{\mathrm{Card}}\nolimits(V)=1$, i.e., the set of
nonterminal symbols is reduced to $S$ then $L$ is reduced to $C_{S}\diamond
L^{\prime}(G)$ and $L^{\prime}(G)$ is finite. We may further assume that there
is a sole terminal rule $S\rightarrow w$, so that $L^{\prime}(G)=\\{w\\}$. By
Theorem 1 one has666By Proposition 1, if ${\mathbf{C}l}(M_{S})$ is algebraic,
then $\\{X\oplus Y^{\mbox{T}}:X\oplus Y\in{\mathbf{C}l}(M_{S})\\}$ is so

${\mathbf{C}l}(\varphi(L))=\\{X\varphi(w)Y^{\mbox{T}}\mid X\oplus
Y\oplus\\{\varphi(w)\\}\in{\mathbf{C}l}(M_{S}\oplus\varphi(w))\\}$ (26)

so that

${\mathbf{C}l}(M_{S}\oplus\varphi(w))={\mathbf{C}l}(M_{S})\oplus{\mathbf{C}l}(\varphi(w))={\mathbf{C}l}(M_{S})\oplus\varphi(w)$

which, by Lemma 5 and Proposition 4, is algebraic. By (26) and Proposition 3,
we conclude that ${\mathbf{C}l}(\varphi(L))$ is effective semialgebraic. The
basis of the induction is thus proved. Now assume $V$ contains more than one
nonterminal symbol. By Theorem 1, Corollary 1 and Eq. (24), we get

${\mathbf{C}l}(\varphi(C_{S})\diamond\varphi(L^{\prime\prime}))=\\{XZY^{\mbox{T}}\mid
X\oplus Y\oplus
Z\in{\mathbf{C}l}(M_{S})\oplus{\mathbf{C}l}(\varphi(L^{\prime\prime}))\\}=$
$\\{XZY^{\mbox{T}}\mid X\oplus Y\oplus
Z\in{\mathbf{C}l}(M_{S})\oplus{\mathbf{C}l}(\varphi(w_{1})\varphi(L_{A_{1}})\cdots\varphi(w_{\ell})\varphi(L_{A_{\ell}})\varphi(w_{\ell+1}))\\}$

By Corollary 1 we have

$\begin{array}[]{ll}&{\mathbf{C}l}(\varphi(w_{1})\varphi(L_{A_{1}})\cdots\varphi(w_{\ell})\varphi(L_{A_{\ell}})\varphi(w_{\ell+1}))\\\
=&\varphi(w_{1}){\mathbf{C}l}(\varphi(L_{A_{1}}))\cdots\varphi(w_{\ell}){\mathbf{C}l}(\varphi(L_{A_{\ell}}))\varphi(w_{\ell+1}))\end{array}$

which shows, via Proposition 1 and by the induction hypothesis, that this
subset is semialgebraic. Then its direct sum with ${\mathbf{C}l}(M_{S})$ is
semialgebraic. We conclude by applying Proposition 3. The second part of the
statement is obtained from the hypothesis by following the same proof. ∎∎

###### Lemma 6

Assume that $L$ is a context-free linear language and the quantum automaton is
rational. Then, for every variable $A$, ${\mathbf{C}l}(M_{A})$ is effective
algebraic.

###### Proof.

Following [4], let us first recall that a subset of a monoid $M$ is _regular_
if it is recognized by some finite $M$-automaton, which differs from an
ordinary finite nondeterministic automaton over the free monoid by the fact
the transitions are labeled by elements in $M$. Further, by [1], the subgroup
generated by a regular subset of a monoid has an effective finite generating
set. Observe now that, if $L$ is a context-free linear language, then $M_{A}$
is a regular submonoid of the group of orthogonal matrices $O_{n}\oplus
O_{n}$. Indeed, it is recognized by the finite $O_{2n}$-automaton whose states
are the nonterminal symbols, the transitions are of the form
$A\stackrel{{\scriptstyle\varphi(a)\oplus\varphi(b)^{\tiny\mbox{T}}}}{{\overrightarrow{\rule{33.62332pt}{0.0pt}}}}B,$
where $A\rightarrow aBb$ is a rule of the grammar and where the initial and
final states coincide with $S$. Hence $\langle M_{A}\rangle$ has an effective
finite generating set and the claim follows by applying to $\langle
M_{A}\rangle$ the algorithm of Derksen et al. [12]. ∎∎

Proposition 9 together with Lemma 6 finally yield.

###### Corollary 2

([7], Prop. 22) If $L$ is a context-free linear language and the quantum
automaton $\cal Q$ is rational, then its closure ${\mathbf{C}l}(\varphi(L))$
is an effective semialgebraic set. As a consequence, it is recursively
decidable whether or not $L\cap|{\cal Q}_{>}|=\emptyset$ holds.

We recall that an intermediate class of languages in between the linear and
the finite index ones, is that of metalinear (or ultralinear) languages ${\cal
L}(Meta_{Lin})$. By definition, a language $L$ is in ${\cal L}(Meta_{Lin})$ if
there exist a context-free grammar $G$ with $L=L(G)$ and an integer
$k\in\mathbb{N}$ such that, in every derivation of $G$, the number of
occurrences of variables in each sentential form does not exceed $k$. The
following corollary holds.

###### Corollary 3

It is recursively decidable whether or not $L\cap|{\cal Q}_{>}|=\emptyset$
holds, if $L\in{\cal L}(Meta_{Lin})$ and $\cal Q$ is a rational quantum
automaton.

###### Proof.

It is known (see [4, 15]) that $L$ is in ${\cal L}(Meta_{Lin})$ if and only if
$L$ is a finite union of finite products of context-free linear languages.
Thus the claim follows from Corollary 2, the closure properties of Section 2.3
and Proposition 7. ∎∎

##  6 Main results

We will prove now that the problem is decidable for two families of languages:
the languages generated by the class of restricted matrix context-free
grammars and, subsequently, the languages generated by context-free monoidal
grammars.

###  6.1 The case of finite index matrix languages

Now we propose a first non trivial extension of the main results of
decidability provided in [7]. Such an extension is based upon the machinery of
Subsection 5, and some combinatorial arguments developed by Choffrut,
Varricchio and the second author in [10] for the study of rational relations.

To this purpose, following [11], we first recall that a matrix context-free
grammar (which we will henceforth simply call matrix grammar) is a tuple
$G=\langle V,\Sigma,M,S\rangle$, where $V$, $\Sigma$, and $M$ are respectively
the finite sets of nonterminals, terminals, and matrix rules, and $S\in V$ is
the start symbol. Each matrix rule $m\in M$ is a finite sequence
$m=(p_{1},\ldots,p_{s})$ where each $p_{i}$, $1\leq i\leq s$, is a context-
free production from $V$ to $(V\cup\Sigma)^{*}$. For $m\in M$, we define
$x\mathrel{\mathop{\Rightarrow}_{m}}y,x,y\in V^{*}$ if
$x=x_{0}\mathrel{\mathop{\Rightarrow}_{p_{1}}}x_{1}\mathrel{\mathop{\Rightarrow}_{p_{2}}}\cdots\mathrel{\mathop{\Rightarrow}_{p_{s}}}x_{s}=y$,
where $\mathrel{\mathop{\Rightarrow}_{p_{i}}}$ is the standard context-free
derivation relation. Let $M^{*}$ be the set of the finite sequences of matrix
rules and $\alpha\in M^{*}$. If $\alpha=\varepsilon$, then
$x\Rightarrow_{\alpha}x,x\in V^{*}$; if one has

$\alpha=m_{1}m_{2}\cdots m_{s}\mbox{\quad
and\quad}x_{0}\mathrel{\mathop{\Rightarrow}_{m_{1}}}x_{1}\mathrel{\mathop{\Rightarrow}_{m_{2}}}\cdots\
x_{s-1}\mathrel{\mathop{\Rightarrow}_{m_{s}}}x_{s},$

with $x_{i}\in V^{*}$, $m_{j}\in M$, $1\leq j\leq s$, $0\leq i\leq s$, then we
write $x_{0}\mathrel{\mathop{\Rightarrow}_{\alpha}}x_{s}$. The _language
generated_ by $G$, $L(G)=\\{w\in\Sigma^{*}\mid
S\mathrel{\mathop{\Rightarrow}_{\alpha}}w\\}$. The following definition is
instrumental.

###### Definition 9

A matrix grammar $G=(V,\Sigma,M,S)$ is said to be restricted linear of index
$k$, or simply restricted, if the set of nonterminals of $G$ has the form
$V=\\{S\\}\cup V^{\prime}$, where $V^{\prime}=V_{1}\cup\dots\cup V_{k},$ and
$V_{i}\cap V_{j}=\emptyset,$ for all $i\neq j$, and a matrix rule of $G$ can
be only of one of the following forms

  * •

$(X_{1}\rightarrow u_{1}Y_{1}v_{1},\ldots,X_{k}\rightarrow u_{k}Y_{k}v_{k})$,
for some $X_{i},Y_{i}\in V_{i},\ u_{i},\ v_{i}\in\Sigma^{*}$, with $1\leq
i\leq k$.

  * •

For every $X_{i}\in V_{i}$ and $1\leq i\leq k$,
$(X_{1}\rightarrow\varepsilon,\ldots,X_{k}\rightarrow\varepsilon)$.

  * •

$(S\rightarrow X_{1}\cdots X_{k})$, for some $X_{i}\in V_{i}$, with $1\leq
i\leq k$.

The main result of this section is the following.

###### Proposition 10

Let $L$ be a language generated by a restricted grammar. Then one has:

  1. i.

${\mathbf{C}l}(\varphi(L))$ is semialgebraic.

  2. ii.

If the quantum automaton ${\cal Q}$ is rational, then
${\mathbf{C}l}(\varphi(L))$ is effective semialgebraic and the $(L,Q)$
Intersection problem is decidable.

###### Proof.

(i) Set ${\cal X}=(V^{\prime})^{k}$ and ${\cal Y}=\\{X_{1}\cdots X_{k}\in{\cal
X}:\exists\ m\in M:m=(S\rightarrow X_{1}\cdots X_{k})\\}$. It is easily
checked that, given $w\in\Sigma^{*}$, $w\in L$ if and only if there exists
some
$\omega=(u_{1},v_{1},u_{2},v_{2},\ldots,u_{k},v_{k})\in(\Sigma^{*})^{2k},$
such that

$w=u_{1}v_{1}u_{2}v_{2}\;\cdots\;u_{k}v_{k},$

and $\omega$ belongs to the set $\cal L$ defined as

${\cal L}=\bigcup_{p\in{\cal Y},\;q\in\cal X}\;{\cal L}_{pq},$ (27)

where, for $p=X_{1}\cdots X_{k},\ q=Y_{1}\cdots Y_{k}$, ${\cal L}_{pq}$ is the
subset of $(\Sigma^{*})^{2k}$ defined as

${\cal L}_{pq}=\\{\;(u_{1},v_{1},\ldots,u_{k},v_{k})\;:\;\exists\ \alpha\in
M^{*}:\ X_{1}\cdots X_{k}\Rightarrow_{\alpha}u_{1}Y_{1}v_{1}\cdots
u_{k}Y_{k}v_{k}\;\\}.$

Let $s=(q_{1},\ldots,q_{n})$ be a repetition-free sequence of elements of
$\cal X$, ie, for every positive integers $i,j$, if $i\neq j$, then $q_{i}\neq
q_{j}$. Clearly, $n$ is less than or equal to the number of states of $\cal X$
and therefore the set $\cal S$ of all repetition-free sequences is finite.
Further, for every $p,q\in\cal X$, let ${\cal S}_{pq}$ be the set

${\cal S}_{pq}=\\{s\in{\cal
S}\;\mid\;s=(q_{1},\ldots,q_{n}),\;q_{1}=p,\;q_{n}=q\\}.$

Now, for every $p,q\in\cal X$, define the subset $E_{pq}$ of
$(\Sigma^{*})^{2k}$ as:

$E_{pq}=\\{\;(u_{1},v_{1},\ldots,u_{k},v_{k})\;:\;\exists\ m\in M:\
X_{1}\cdots X_{k}\Rightarrow_{m}u_{1}Y_{1}v_{1}\cdots u_{k}Y_{k}v_{k}\;\\},$

and the subset $C_{q}$ of $(\Sigma^{*})^{2k}$ as:

$C_{q}=\\{\;(u_{1},v_{1},\ldots,u_{k},v_{k})\;:\;\exists\ \alpha\in M^{*}:\
X_{1}\cdots X_{k}\Rightarrow_{\alpha}u_{1}Y_{1}v_{1}\cdots
u_{k}Y_{k}v_{k}\;\\}.$

One easily checks that $C_{q}$ is a submonoid of the monoid
$(\Sigma^{*})^{2k}$. For every $s=(q_{1},\ldots,q_{n})\in\cal S$, define the
(possibly empty) subset ${\cal L}_{s}$ of $(\Sigma^{*})^{2k}$ as:

${\cal L}_{s}=C_{q_{1}}E_{q_{1}q_{2}}C_{q_{2}}\cdots
C_{q_{n-1}}E_{q_{n-1}q_{n}}C_{q_{n}}$ (28)

By using the very same argument of [10], Theorem 2, one can prove that

${\cal L}_{pq}=\bigcup_{s\in{\cal S}_{pq}}\ {\cal L}_{s}$ (29)

Let now consider the morphism

$\widehat{\varphi}:(\Sigma^{*})^{2k}\rightarrow O_{2nk},$

which maps every element $\omega=(u_{1},v_{1},\ldots,u_{k},v_{k})$ into the
orthogonal matrix

$\widehat{\varphi}(\omega)=\varphi(u_{1})\ \oplus\ \varphi(v_{1})\ \oplus\
\cdots\ \oplus\ \varphi(u_{k})\ \oplus\ \varphi(v_{k}),$

of the $2k$-fold product $O_{2nk}$ of $O_{n}.$

Now we prove that ${\mathbf{C}l}({\varphi}(L))$ is semialgebraic. By
Proposition 3, it is enough to show that ${\mathbf{C}l}(\widehat{\varphi}(\cal
L))$ is so. To this purpose, with an arbitrary nonterminal $q\in{\cal X}$ of
$G$, associate the subset $M_{q}$ of $O_{2nk}$ defined as

$\\{\varphi(u_{1})\oplus\varphi(v_{1})^{\mbox{T}}\oplus\cdots\oplus\varphi(u_{k})\
\oplus\ \varphi(v_{k})^{\mbox{T}}\mid(u_{1},v_{1},\ldots,u_{k},v_{k})\in
C_{q}\\}$ (30)

By using the very same argument of Lemma 5, one proves that $M_{q}$ is a
monoid and its closure ${\mathbf{C}l}(M_{q})$ is an algebraic group. From
this, by Proposition 1, it follows that
${\mathbf{C}l}(\widehat{\varphi}({C}_{q}))$ is algebraic as well. This
implies, via Corollary 1 and Proposition 3, that every set
${\mathbf{C}l}(\widehat{\varphi}({\cal L}_{s}))$ of (28) is semialgebraic.
Then the semialgebraicity of ${\mathbf{C}l}(\widehat{\varphi}(\cal L))$
follows, by applying Proposition 1, from the last condition and (27), (29).

(ii) Assume that the quantum automaton ${\cal Q}$ is rational. First we prove
that ${\mathbf{C}l}(M_{q}))$ is effective algebraic. One proceeds as in the
proof of Lemma 6. Indeed, since $L$ is generated by a restricted matrix
grammar, then $M_{q}$ is a regular submonoid of $O_{2nk}$. Precisely, it is
recognized by the finite $O_{2nk}$–automaton whose states are the elements of
$\cal X$, the initial and final states coincide with $q$, and the transitions
are of the form

$e=(s\stackrel{{\scriptstyle\ell(e)}}{{\overrightarrow{\rule{14.85184pt}{0.0pt}}}}t),\quad
s,t\in\cal X,$

where, being $s=X_{1}\cdots X_{k},\ t=Y_{1}\cdots Y_{k}$, there exists $m\in
M$ such that

$X_{1}\cdots X_{k}\Rightarrow_{m}u_{1}Y_{1}v_{1}\cdots u_{k}Y_{k}v_{k},$

with $\ell(e)\in O_{2nk}$ defined as

$\ell(e)=\varphi(u_{1})\oplus\varphi(v_{1})^{\mbox{T}}\oplus\cdots\oplus\varphi(u_{k})\
\oplus\ \varphi(v_{k})^{\mbox{T}}.$

Hence $M_{q}$ is regular and the group $\langle M_{q}\rangle$ has an effective
finite generating set. By applying to $\langle M_{q}\rangle$ the algorithm of
Derksen et al. [12], one gets an effective presentation of
${\mathbf{C}l}(M_{q})$. From this, by Proposition 1, it follows that
${\mathbf{C}l}(\widehat{\varphi}({C}_{q}))$ is effective algebraic as well.
Finally, since all the steps of the proof (i) are effective, the fact that
${\mathbf{C}l}(\widehat{\varphi}({C}_{q}))$ is effective algebraic implies
that ${\mathbf{C}l}({\varphi}(L))$ is so. The claim follows by applying
Proposition 7. ∎∎

We now discuss some straightforward corollaries of Proposition 10. First,
remark that, by applying the proposition to the matrix grammars of index k=1,
we obtains [7], Prop. 22 (cf Corollary 2).

We recall that a _bounded semilinear_ language is a finite union of _linear_
languages which are languages of the form

$L=\\{u_{1}^{n_{1}}\cdots u_{k}^{n_{k}}\mid(n_{1},\ldots,n_{k})\in{R}\\}$ (31)

for some fixed words $u_{i}\in\Sigma^{*}$ for $i=1,\ldots,k$ and
$R\subseteq\mathbb{N}^{k}$ is a linear set, i.e., there exists ${\bf
v}_{0},{\bf v}_{1},\ldots,{\bf v}_{\ell}\in\mathbb{N}^{k}$ such that

$R=\\{{\bf v}_{0}+\lambda_{1}{\bf v}_{1}+\cdots+\lambda_{\ell}{\bf
v}_{\ell}\mid\lambda_{1},\ldots,\lambda_{\ell}\in\mathbb{N}\\}$

###### Lemma 7

Every bounded semi-linear language can be generated by a restricted grammar.

###### Proof.

It is enough to prove the claim for an arbitrary language $L$ of the form
(31). It is checked that $L$ is generated by the restricted grammar $G=\langle
V,\Sigma,M,S\rangle$, where $V=\\{S,X_{1},\ldots,X_{k}\\}$ and $M$ is given by
the matrix rules

  * •

$(S\rightarrow X_{1}\cdots X_{k})$.

  * •

$(S\rightarrow u_{1}^{{\bf v}_{01}}X_{1}\cdots u_{k}^{{\bf v}_{0k}}X_{k})$,
with ${{\bf v}_{0}=({\bf v}_{01}},\ldots,{\bf v}_{0k})$.

  * •

For every $i=1,\ldots,\ell,$ $(X_{1}\rightarrow u_{1}^{{\bf
v}_{i1}}X_{1},\ldots,X_{k}\rightarrow u_{k}^{{\bf v}_{ik}}X_{k})$
with ${{\bf v}_{i}=({\bf v}_{i1}},\ldots,{\bf v}_{ik}),\ 1\leq i\leq k$. ∎

∎

Proposition 10 and Lemma 7 provide a new proof of the following.

###### Corollary 4

([7], Prop. 21) If $L$ is bounded semilinear then its closure
${\mathbf{C}l}(\varphi(L))$ is semialgebraic. Furthermore, if the quantum
automaton ${\cal Q}$ is rational, the $(L,Q)$ Intersection problem is
decidable.

We finally observe that Proposition 10 is a non trivial extension of Corollary
2 and Corollary 4. Indeed the following example provides languages, neither
bounded nor context-free, defined by restricted grammars.

###### Example 2

Let $L_{k}$, with $k\in\mathbb{N}$, be the language over $\Sigma=\\{a,b\\}$
given by $L_{k}=\\{u^{k}:u\in\Sigma^{*}\\}$. It is easily checked that $L_{k}$
can be generated by the restricted grammar $G=\langle V,\Sigma,M,S\rangle$,
where $V=\\{S,X_{1},\ldots,X_{k}\\}$, and $M$ is given by the matrix rules
$(S\rightarrow X_{1}\cdots X_{k})$,
$(X_{1}\rightarrow\varepsilon,\ldots,X_{k}\rightarrow\varepsilon)$, and, for
every $\sigma\in\Sigma$, $(X_{1}\rightarrow\sigma
X_{1},\ldots,X_{k}\rightarrow\sigma X_{k})$.

###  6.2 The case of monoidal languages

We start with the following definition that is instrumental for this section.

###### Definition 10

A grammar $G=\langle V,\Sigma,P,S\rangle$ is said to be monoidal of index $k$
if it is the composition

$G={\cal G}_{1}\circ{\cal G}_{2}\circ\cdots\circ{\cal G}_{k},$

of $k$ families of linear grammars where the productions of $G$ satisfy the
following conditions:

  * •

if $\ (X\rightarrow u)\in P,\,\ u\in\Sigma^{*}$ (terminal production) then
$u=\varepsilon$

  * •

if $\ (X\rightarrow uYv)\in P$, where $X,Y$ are distinct variables of a
grammar in ${\cal G}_{i},\ 1\leq i\leq k,$ then $u=v=\varepsilon.$

A language is said to be monoidal if it is generated by a monoidal grammar of
index $k$, for some $k\in\mathbb{N}$. The main result of this section is the
following.

###### Proposition 11

Let $(L,Q)$ be a pair where $Q$ is a rational quantum automaton and $L$ is a
language generated by a monoidal grammar $G={\cal G}_{1}\circ{\cal
G}_{2}\circ\cdots\circ{\cal G}_{k}$. If the Zariski closures of the monoids of
cycles of the grammars of ${\cal G}_{k}$ are irreducible, then
${\mathbf{C}l}(\varphi(L))$ is effective semialgebraic.

We will do the proof of Proposition 11 for $k\leq 2$, i.e., for a monoidal
grammar $G={\cal G}_{1}\circ{\cal G}_{2}$ of index $2$, since, by (17), the
general case is treated with the same argument. The proof is technically
structured in the following lemmata.

Now we find useful to recall a notation introduced in Section 2.4.

Notation. Given a subset $\cal A$ of the group $O_{m}$ of orthogonal matrices
(over $\mathbb{R}$), we write

${\cal A}\in({\cal H})$ (32)

if $\cal A$ is a finite union of irreducible, effective algebraic sets, every
one of which contains the identity matrix $I$ of $O_{m}$.

###### Lemma 8

Let $G={\cal G}_{1}$ be a monoidal grammar of index $1$ and let $L=L(G)$. If
the Zariski closure of all the monoids of cycles of $G$ are irreducible,
effective algebraic sets, then there exist a set $H\in({\cal H})$ and a
regular map $\Psi$ such that

${\mathbf{C}l}(\varphi(L))=\Psi(H).$

In particular ${\mathbf{C}l}(\varphi(L))$ is effective semialgebraic and
contains $I$.

###### Proof.

Let $G=\langle V,\Sigma,P,S\rangle$ be a monoidal grammar of index $1$. We
rerun the proof of Proposition 9 for $G$. We proceed thus on
$\mathop{\mathrm{Card}}\nolimits(V)$. If
$\mathop{\mathrm{Card}}\nolimits(V)=1,$ i.e., $V=\\{S\\}$, then $G$ has a sole
monoid of cycles $M_{S}$. Taking into account (26) and the form of the
terminal productions of $G$, one has
${\mathbf{C}l}(\varphi(L_{S}))=\Psi({\mathbf{C}l}(M_{S}))$, where
$\Psi(X\oplus Y):=XY^{\mbox{T}}.$ From this and the fact that, by hypothesis,
${\mathbf{C}l}(M_{S})$ is irreducible, it follows the claim in this case. The
basis of induction is proved.

Let us prove the inductive step. By Proposition 8, and taking into account the
form of the productions of $G$, one has

$L_{S}=\bigcup_{i=1}^{m}\,C_{S}\diamond L_{A_{i}},$ (33)

where, for every $i=1,\ldots,m$, $A_{i}\in V^{\prime}=V\setminus\\{S\\}$.
Relation (33) now implies

${\mathbf{C}l}(\varphi(L_{S}))=\bigcup_{i=1}^{m}\,{\mathbf{C}l}(M_{S}\diamond\varphi(L_{A_{i}})).$

By the induction hypothesis, for every $i=1,\ldots,m,$
${\mathbf{C}l}(\varphi(L_{A_{i}}))=\Psi^{\prime}(H_{i})$, where
$H_{i}\in({\cal H})$, $\Psi^{\prime}$ is a regular map (not depending on the
variable $A_{i}$) and ${\mathbf{C}l}(\varphi(L_{A_{i}}))$ contains $I$. From
this, by a straightforward computation, one gets

${\mathbf{C}l}(\varphi(L_{S}))=\Psi^{\prime\prime}(\,\bigcup_{i=1}^{m}\,{\mathbf{C}l}(M_{S})\oplus
H_{i}\,),$ (34)

where

$\Psi^{\prime\prime}(X\oplus Y\oplus Z):=X\Psi^{\prime}(Z)Y^{\mbox{T}}.$

Since ${\mathbf{C}l}(M_{S})$ is effective algebraic and $H_{i}\in({\cal
H}),1\leq i\leq m$, then, by Proposition 5, the set
$\bigcup_{i=1}^{m}\,{\mathbf{C}l}(M_{S})\oplus H_{i}\in({\cal H})$ as well.
Finally the claim comes from (34) taking into account that the map
$\Psi^{\prime\prime}$ is regular. ∎∎

###### Remark 3

Note that the map $\Psi$ of the statement of Lemma 8 does not depend upon the
variable used as axiom of $G$.

Let ${\cal G}_{1}=\langle V_{1},\Sigma_{1},P_{1},S\rangle$ be the first
grammar of the composition $G={\cal G}_{1}\circ{\cal G}_{2}$. Let
$\Sigma_{1}^{*}\times\Sigma_{1}^{*}$ be the multiplicative monoid of binary
relations on $\Sigma_{1}^{*}$ and let $\Pi(O_{n}\oplus O_{n})$ be the
multiplicative monoid of subsets of $O_{n}\oplus O_{n}$. Define now the
morphism between the two monoids

$\zeta:\ \Sigma_{1}^{*}\times\Sigma_{1}^{*}\ \longrightarrow\ \Pi(O_{n}\oplus
O_{n})$

as: for every $(u,v)\in\Sigma_{1}^{*}\times\Sigma_{1}^{*}$, with
$u=A_{1}\cdots A_{s},\ v=B_{1}\cdots B_{t},\ A_{i},B_{i}\in\Sigma_{1}$

$\zeta(u,v)\ =\ (\varphi(L_{A_{1}})\cdots\varphi(L_{A_{s}})\ \oplus\
\varphi(L_{B_{1}})^{\mbox{T}}\cdots\varphi(L_{B_{t}})^{\mbox{T}})$ (35)

where, for every $i=1,\ldots,t$, $\varphi(L_{B_{i}})^{\mbox{T}}$ denotes the
set of matrices

$\\{m^{\mbox{T}}\ :\ m\in\varphi(L_{B_{i}})\\}.$ (36)

The following lemma holds.

###### Lemma 9

For every $S\in V_{1}$, there exists an effective computable regular subset
$\cal R$ of $\ \Sigma_{1}^{*}\times\Sigma_{1}^{*}$ such that
$M_{S}=\zeta({\cal R})$.

###### Proof.

Let us first define the set

$\widehat{C}_{S}=\\{(\alpha,\beta)\in\Sigma_{1}^{*}\times\Sigma_{1}^{*}:(\alpha,\beta^{\sim})\in
C_{S}\\},$

where $\beta^{\sim}$ denotes the mirror image of $\beta$. Observe that
$\widehat{C}_{S}$ is a submonoid of $\Sigma_{1}^{*}\times\Sigma_{1}^{*}$.
Moreover one has

$M_{S}=\zeta(\widehat{C}_{S}).$

Indeed, let us check $M_{S}\subseteq\zeta(\widehat{C}_{S}).$ If
$\varphi(u)\oplus\varphi(v)^{\mbox{T}}\in M_{S}$, then
$S\displaystyle\mathop{\Rightarrow}^{*}uSv$. Since $G={\cal G}_{1}\circ{\cal
G}_{2}$, the last derivation can be rewritten as

$S\displaystyle\mathop{\Rightarrow}^{*}\alpha S\beta$ (37)

where (37) is a derivation of ${\cal G}_{1}$ and

$\alpha\displaystyle\mathop{\Rightarrow}^{*}u,\quad\quad\beta\displaystyle\mathop{\Rightarrow}^{*}v,$
(38)

where both the derivations of (38) are in the grammars of ${\cal G}_{2}.$ Now
set $\alpha=A_{1}A_{2}\cdots A_{s},$ and $\beta=B_{s}B_{s-1}\cdots B_{1}$,
with $A_{i},B_{i}\in\Sigma_{1}\cup\\{\varepsilon\\},s\geq 0$. From (38), one
then has

$u=u_{1}\cdots u_{s},\quad\quad v=v_{s}\cdots v_{1},$

where, for every $i=1,\ldots,s,$ $u_{i}\in L_{A_{i}},$ and $v_{i}\in
L_{B_{i}}$. From this, one has

$\varphi(u)\in\varphi(L_{A_{1}})\cdots\varphi(L_{A_{s}}),\quad\quad\varphi(v)^{\mbox{T}}\in\varphi(L_{B_{1}})^{\mbox{T}}\cdots\varphi(L_{B_{t}})^{\mbox{T}}.$
(39)

Finally observe that, by (37), $(\alpha,\beta)\in C_{S}$ so that
$(\alpha,\beta^{\sim})\in\widehat{C}_{S}$. By (39) the latter implies
$\varphi(u)\oplus\varphi(v)^{\mbox{T}}\in\zeta(\widehat{C}_{S})$. Hence
$M_{S}\subseteq\zeta(\widehat{C}_{S})$. The other inclusion is checked
similarly.

Since ${\cal G}_{1}$ is a linear grammar, by a well-known construction (cf
[4]), one has that $\widehat{C}_{S}$ is an effective computable rational
binary relation on $\Sigma_{1}^{*}$. The lemma is proved. ∎∎

###### Lemma 10

For every $A\in V_{1}$, ${\mathbf{C}l}(M_{A})\in({\cal H}).$ In particular,
${\mathbf{C}l}(M_{A})$ is effective algebraic.

###### Proof.

By Lemma 9, for every $A\in V_{1}$, there exists an effective computable
regular subset $\cal R$ of $\ \Sigma_{1}^{*}\times\Sigma_{1}^{*}$ such that
$M_{A}=\zeta({\cal R})$. We will prove the following slightly more general
claim:

Claim. For every regular subset $\cal R$ of
$\Sigma_{1}^{*}\times\Sigma_{1}^{*}$, ${\mathbf{C}l}(\zeta({\cal R}))$
contains $I$ and ${\mathbf{C}l}(\zeta({\cal R}))=\Psi(H)$ for some $H\in({\cal
H})$ (cf (32)) and regular map $\Psi$. Further, if ${\cal R}=R^{*}$, then
${\mathbf{C}l}(\zeta({\cal R}))\in({\cal H})$.

We first show the claim for a finite set $\cal R$. We may suppose $\cal R$
$=\\{r\\}$, where $r=(\alpha,\beta)$ with $\alpha=A_{1}A_{2}\cdots A_{s},\ $
$\beta=B_{1}\cdots B_{t}$, $A_{i},B_{i}\in\Sigma_{1},\ s,t\geq 0$. We assume
fist that $\alpha$ and $\beta$ have the same length, i.e., $s=t$. By (35), the
fact that $\zeta$ is a monoid morphism and Corollary 1, one gets

${\mathbf{C}l}(\zeta({\cal R}))=\
({\mathbf{C}l}(\varphi(L_{A_{1}}))\cdots{\mathbf{C}l}(\varphi(L_{A_{s}}))\
\oplus\
{\mathbf{C}l}(\varphi(L_{B_{1}}))^{\mbox{T}}\cdots{\mathbf{C}l}(\varphi(L_{B_{s}}))^{\mbox{T}}),$

taking into account that, for an arbitrary set $\cal A$ of orthogonal
matrices, for the set (36), one has ${\mathbf{C}l}({\cal
A}^{\mbox{T}})={\mathbf{C}l}({\cal A})^{\mbox{T}}$. By Lemma 8, the previous
formula gives

${\mathbf{C}l}(\zeta({\cal R}))=\ (\Psi(H_{1})\cdots\Psi(H_{s})\ \oplus\
\Psi(G_{1})^{\mbox{T}}\cdots\Psi(G_{s})^{\mbox{T}}),$

where $\Psi$ is a regular map and, for every $i=1,\ldots,s$,
$H_{i},G_{i}\in({\cal H})$.

Since each $\Psi(H_{i})$ and $\Psi(G_{i})$ of the last formula, contain $I$ so
holds for ${\mathbf{C}l}(\zeta({\cal R}))$. Set $H=H_{1}\oplus\cdots\oplus
H_{s}\oplus G_{1}\oplus\cdots\oplus G_{s}$ and observe that, by Proposition 5,
$H\in({\cal H})$. Then ${\mathbf{C}l}(\zeta({\cal R}))=\ \Psi^{\prime}(H)$,
where $\Psi^{\prime}$ is the regular map defined as

$\Psi^{\prime}(X_{1}\oplus\cdots\oplus X_{s}\oplus Y_{1}\oplus\cdots\oplus
Y_{s})=(\Psi(X_{1})\cdots\Psi(X_{s})\oplus\Psi(Y_{1})^{\mbox{T}}\cdots\Psi(Y_{s})^{\mbox{T}}).$

This proves that the claim for $\cal R$ $=\\{r\\}$. Finally, if $s>t$, then we
can write the word $\beta=B_{1}\cdots B_{t}$ as $\beta=B_{1}\cdots B_{s}$,
with $B_{j}=\varepsilon$, for $j=t+1,\ldots,s$. Afterwards, set
$L_{B_{j}}=\\{\varepsilon\\}$ and $\varphi(L_{B_{j}})=\\{I\\}$, $t+1\leq j\leq
s$. Then one proceeds to prove the claim, by repeating the argument above for
$s=t$.

We now prove the claim according to the following cases:

$\mbox{(i)}\;\;{\cal R}={\cal R}_{1}\cup{\cal
R}_{2},\;\;\;\;\;\;\;\;\mbox{(ii)}\;\;{\cal R}={\cal R}_{1}{\cal
R}_{2},\;\;\;\;\;\;\;\;\mbox{(iii)}\;\;{\cal R}={\cal R}_{1}^{*},$

where

${\mathbf{C}l}(\zeta({\cal
R}_{1}))=\Psi_{1}(H_{1}),\quad{\mathbf{C}l}(\zeta({\cal
R}_{2}))=\Psi_{2}(H_{2}),$ (40)

with $H_{1},H_{2}\in({\cal H})$ and $\Psi_{1},\Psi_{2}$ being regular maps.

(i) By (40) one gets ${\mathbf{C}l}(\zeta({\cal R}))=\Psi(H_{1}\cup H_{2})$,
and the claim comes from $H_{1}\cup H_{2}\in({\cal H})$.

(ii) By Corollary 1 and the fact that $\zeta$ is a monoid morphism, (40)
yields ${\mathbf{C}l}(\zeta({\cal R}))=\Psi_{1}(H_{1})\Psi_{2}(H_{2}).$ From
this, since $I\in\Psi_{1}(H_{1}),\Psi_{2}(H_{2})$ then
$I\in{\mathbf{C}l}(\zeta({\cal R}))$. Now, observe that, by Propositions 1, 4,
and 5, the condition $H_{1},H_{2}\in({\cal H})$ implies $H_{1}\oplus
H_{2}\in({\cal H})$. The claim follows from the fact that

$\Psi_{1}(H_{1})\Psi_{2}(H_{2})=\Psi(H_{1}\oplus H_{2}),$

where $\Psi$ is the regular map defined as $\Psi(X\oplus
Y):=\Psi_{1}(X)\Psi_{2}(Y)$.

(iii) Since ${\cal R}=R^{*}$ and the fact that $\zeta$ is a monoid morphism,
then one has

${\mathbf{C}l}(\zeta({\cal
R}))={\mathbf{C}l}(\zeta({R^{*}}))={\mathbf{C}l}(\zeta({R})^{*}).$

Observe that, from this, it trivially follows that ${\mathbf{C}l}(\zeta({\cal
R}))$ contains $I$.

Now taking into account that, by Corollary 1, for an arbitrary set $\cal X$,

${\mathbf{C}l}({\cal X}^{*})={\mathbf{C}l}({\mathbf{C}l}({\cal X})^{*}),$ (41)

one has

${\mathbf{C}l}(\zeta({\cal R}))={\mathbf{C}l}({\mathbf{C}l}(\zeta({R}))^{*}).$

By Theorems 2 and 3, one has

${\mathbf{C}l}({\mathbf{C}l}(\zeta({R}))^{*})=\overline{{\mathbf{C}l}(\zeta({R}))^{*}},$
(42)

where $\overline{{\mathbf{C}l}(\zeta({R}))^{*}}$ is the Zariski closure of
${\mathbf{C}l}(\zeta({R})^{*})$. Recall that, by (40), one has
${\mathbf{C}l}(\zeta({R}))=\Psi(H)$, where $\Psi$ is a regular map and
$H\in({\cal H})$. This fact and (42) now implies

${\mathbf{C}l}(\zeta({\cal R}))=\overline{\Psi(H)^{*}}.$

Since $H\in({\cal H})$, we can write $H=\bigcup_{i=1}^{k}\ H_{i}$ as a finite
union of irreducible effective algebraic sets $H_{i}$, every one of which
containing the identity matrix $I$. This, together with Lemma 2, implies

${\mathbf{C}l}(\zeta({\cal R}))\ =\ \overline{(\Psi(H_{1})\ \cdots\
\Psi(H_{k}))^{*}}.$

Observe that in the formula above, we can write $\Psi(H_{1})\ \cdots\
\Psi(H_{k})$ as
$\widehat{\Psi}(H_{1}\oplus\cdots\oplus H_{k})$, where $\widehat{\Psi}$ is the
regular map defined as $\widehat{\Psi}(X_{1}\oplus\cdots\oplus
X_{k})=\Psi(X_{1})\cdots\Psi(X_{k})$. Hence we get

${\mathbf{C}l}(\zeta({\cal R}))\ =\overline{(\widehat{\Psi}(H))^{*}},$

where, again, $H=(H_{1}\oplus\cdots\oplus H_{k})\in({\cal H})$ as one can
easily checks. The claim follows by applying Proposition 6. This completes the
proof. ∎∎

We are now able to prove the main result of this section.

Proof of Proposition 11: As remarked before, it is enough to prove the claim
for $k\leq 2$ since, by (17), the general case is treated with the same
argument. Let $G=\langle V,\Sigma,P,S\rangle$ and observe that, for every
$A\in V$, ${\mathbf{C}l}(M_{A})$ is effective algebraic by hypothesis if $k=1$
and, by Lemma 10, if $k=2$. The claim now follows from Proposition 9. ∎

By Propositions 1 and 7, immediate corollaries of Proposition 11 are the
following.

###### Corollary 5

If the pair $(L,Q)$ satisfies the hypothesis of Proposition 11, then the
$(L,Q)$ Intersection problem is decidable.

###### Corollary 6

Let $(L,Q)$ be a pair where $Q$ is a rational quantum automaton and $L$ is a
finite union $L=\bigcup_{i\in{\cal I}}L_{i},$ of monoidal languages, every one
of which is such that the corresponding pair $(L_{i},Q)$ satisfies the
hypothesis of Proposition 11. Then the $(L,Q)$ Intersection problem is
decidable.

An example describing the main steps of Proposition 11 will be given in
Section 8.

##  7 Concluding remarks and open problems

We finally address some questions arising from this study.

[$\alpha$]  One could extend Proposition 11 to a broader class of quantum
automata. In this context, the construction of the decidability procedure
would require the computation of the Zariski closure of a group $G$ of
matrices that is algebraically presented, i.e. $G$ admits a set of generators
that is algebraic itself. It may be of interest to investigate conditions
assuring the extension of the algorithms of [12, 17, 25] for such groups.

[$\beta$]  It is open whether the $(L,Q)$ Intersection problem is decidable
for context-free languages. We conjecture that the answer to this problem is
negative. An approach may be to reduce the problem to a so called “birdie
problem” [30] (cf also [16], Ch. 8). In such a problem, assuming the
feasibility of the computation of the Zariski closure of the groups above, one
gets, as a consequence, the decidability of some unsolvable problem.

[$\gamma$]  The $(L,Q)$ Intersection problem is decidable for bounded semi-
linear languages. It may be of interest to get extensions of this result for
the broader class of languages accepted by the reversal bounded non
deterministic counter machines [18]. This extension could exploit a
characterization of such languages provided by Ibarra in [19] in terms of some
special combinatorial systems called RLGMC-grammars (right-linear grammar with
multi-counters). Essentially, a RLGMC-grammar is a regular grammar that
associates with each derivation a weight, i.e. a vector in the additive monoid
$\mathbb{N}^{d}$. Then a derivation is considered successful if the
corresponding weight belongs to the monoid generated by $\bf 1^{d}$
$=(1,1,\ldots,1)$. Here the main bulk is the construction of a formula (see
Proposition 7) based on the computation of the Zariski closure of the
Intersection of two finitely generated monoids of matrices. The intrinsic
difficulty to control the accumulation points of the set – i.e., to exclude
those one not coming from the effective functioning of the machines – makes
such a computation a non trivial task.

##  8 Technical details and Examples

We rerun the proofs of Propositions 6 and 11 on the Example 1 of Sec. 4.2.

Example 1 (continued) Let $\cal L$ be the language over the alphabet
$\\{a,b\\}$ given by

${\cal L}=\\{a^{n}b^{n}:n\in\mathbb{N}\\}^{*}\ =\ \\{a^{n_{1}}b^{n_{1}}\cdots
a^{n_{p}}b^{n_{p}}\ :\ n_{1},\ldots,n_{p},\ p\in\mathbb{N}\\}.$

Since $\cal L=$ $L^{*},$ with $L=\\{a^{n}b^{n}:n\in\mathbb{N}\\}$, then

$\mathbf{C}l{(\varphi({\cal
L}))}=\mathbf{C}l{(\varphi({L}^{*}))}=\mathbf{C}l{(\varphi({L})^{*})},$

where $\varphi$ is the morphism (4) of the quantum automaton. Recall that
$\mathbf{C}l{({\cal A}))}$ and $\overline{{\cal A}}$ denote, respectively, the
Euclidean and the Zariski closure of a set $\cal A$. By Theorems 2 and 3, one
has $\mathbf{C}l{(\varphi({L})^{*})}=\overline{\varphi({L})^{*}}$. This
implies $\mathbf{C}l{(\varphi({\cal L}))}=\overline{\Psi({G})^{*}},$ where

  * •

$G=M^{*}$ is the monoid generated by the matrix $M\in O_{n}\oplus O_{n}$

$M=\varphi(a)\oplus\varphi(b)=\left(\begin{array}[]{cc}\varphi(a)&0\\\
0&\varphi(b)\end{array}\right)$

  * •

$\Psi$ is the regular map defined as $\Psi(A\oplus B):=AB$.

We now prove that, if $\overline{G}$ is irreducible and effective algebraic,
then $\overline{\Psi({G})^{*}}$ is in $(\cal H)$ and thus
$\mathbf{C}l{(\varphi({\cal L}))}$ is effective algebraic as well.

For this purpose, observe first that $\Psi:O_{n}\oplus O_{n}\rightarrow O_{n}$
is a regular and thus a continuous map. This implies that

$\Psi(\overline{G})\subseteq\overline{\Psi(G)},$

which, in turn, implies

$\overline{\Psi(\overline{G})}\ =\ \overline{\Psi(G)}.$ (43)

Let $H_{1}=\overline{\Psi(\overline{G})}$. By Lemma 1, $H_{1}$ is an algebraic
irreducible set. Moreover, being $G$ a group, one has $I\in\Psi(G)$ so $I\in
H_{1}$. Since $G$ is finitely generated as a monoid, then, by using Derksen’s
algorithm, one can effectively calculate $\overline{G}$. Afterwards, following
[12], Sec. 3.1, by using Gröbner bases techniques, since $\overline{G}$ is
effective algebraic, then one can effectively compute $H_{1}$.

Let $H_{2}=\overline{H_{1}\cdot H_{1}}$. Observe first that $I\in H_{1}$
implies $I\in H_{2}$. Similarly to the previous case, one observes that, for
arbitrary subsets ${\cal A,B}$ of $O_{n}$

$\overline{\overline{\cal A}\cdot\overline{B}}\ =\ \overline{\cal A\cdot B}.$
(44)

This implies that $\overline{\mbox{m}(\overline{{\cal A}},\overline{{\cal
B}})}=\overline{\mbox{m}({\cal A},{\cal B})}.$ By using the very same argument
for $H_{1}$ one verifies that $H_{2}$ is an irreducible effective algebraic
set. Moreover, by (43) and (44), one has $H_{2}=\overline{\Psi(G)^{2}}$.

Finally, let us define recursively the family $\\{H_{i}\\}_{i\geq 1}$ of sets
of $O_{n}$, where $H_{0}=\\{I\\}$ and, for every $i\geq 1$,
$H_{i}=\overline{H_{i-1}\cdot H_{1}}.$ Getting an ascending chain

$H_{1}\;\subseteq\;H_{2}\;\subseteq\;\cdots\;H_{i}\;\subseteq\;\cdots$

of irreducible, effective algebraic sets, then there exists some
$m\in\mathbb{N}$ such that

$H_{m+1}\ =\ \overline{\Psi({G})^{m\ +\ 1}}\ =\ \overline{\Psi({G})^{m}}\ =\
H_{m}.$ (45)

Finally let ${\cal X}=\bigcup_{i\geq 1}\ H_{i}$. By (45), $\overline{\cal
X}=H_{1}\cup\cdots\cup H_{m}$. On the other hand, since, for every $i\geq 1$,
$H_{i}=\overline{\Psi(G)^{i}}$, then it is checked that

$\overline{\cal X}=H_{1}\cup\cdots\cup H_{m}=\overline{\Psi(G)^{*}}.$

Hence $\overline{\Psi(G)^{*}}$ is effective algebraic.

## References

  * [1] A. V. Anisimov, F. D. Seifert. Zur algebraischen Charakteristik der durch Kontext-freie Sprachen definierten Gruppen. Elektron. Inform. Verarb. u. Kybern. 11, 695-702, 1975.
  * [2] G. Baron, W. Kuich, The Characterization of Nonexpansive Grammars by Rational Power Series, _Information and Control,_ 48, 109–118 1981.
  * [3] S. Basu, R. Pollack, and M. -F. Roy. Algorithms in Real Algebraic Geometry. Springer, Berlin, 2003.
  * [4] J. Berstel. Transductions and Context-Free Languages. Teubner, Stuttgart, 1979.
  * [5] A. Bertoni, C. Mereghetti, and B. Palano. Quantum Computing: 1-Way Quantum Automata, in Proceedings of DLT 2003, Developments in Language Theory, Lecture Notes in Computer Science, Vol. 6224, pp. 1-20, Springer, Berlin, 2003.
  * [6] A. Bertoni, C. Choffrut, and F. D’Alessandro. Quantum finite automata and linear context-free languages, in Proceedings of DLT 2013, Developments in Language Theory, Lecture Notes in Computer Science, Vol. 7907, pp. 82-93, Springer, Berlin, 2013.
  * [7] A. Bertoni, C. Choffrut, and F. D’Alessandro. On the decidability of the intersection problem for quantum automata and context-free languages, Internat. J. Found. Comput. Sci., 25, 1065-1081, 2014.
  * [8] V. D. Blondel, E. Jeandel, P. Koiran, and N. Portier. Decidable and Undecidable Problems about Quantum Automata. SIAM J. Comput., 34, 1464-1473, 2005.
  * [9] J. Cassaigne, F. Nicolas. On the decidability of semigroup freeness. RAIRO Theor. Informatics Appl., 46, 355-399, 2012.
  * [10] C. Choffrut, F. D’Alessandro and S. Varricchio. Bounded rational languages of trace monoids, Theory of comput. sys., 46, 351-369, 2010.
  * [11] J. Dassow, G. Paun. Regulated Rewriting in Formal Language Theory. EATCS Monographs in Theoretical Computer Science, vol. 18, Springer, 1989.
  * [12] H. Derksen, E. Jeandel, and P. Koiran. Quantum automata and algebraic groups. J. Symb. Comput., 39, 357-371, 2005.
  * [13] M. Geck. An Introduction to Algebraic Geometry and Algebraic Groups. Oxford University Press, 2003.
  * [14] S. Ginsburg, E. H. Spanier. Derivation-bounded languages. J. Comput. System Sci. 2 (3), 228-250, 1968.
  * [15] S. Ginsburg, _The mathematical theory of context-free languages_ , Mc Graw-Hill, New York, 1966.
  * [16] M. A. Harrison. Introduction to Formal Language Theory. Addison-Wesley Publishing Co., Reading, Mass 1978.
  * [17] E. Hrushovski, J. Ouaknine, A. Pouly, and J. Worrell. On Strongest Algebraic Program Invariants. J. ACM, 70, 1-22, 2023.
  * [18] O. H. Ibarra. Reversal-bounded multicounter machines and their decision problems, J. ACM, 25, 116–133, 1978.
  * [19] O. H. Ibarra. Grammatical characterizations of NPDAs and VPDAs with counters. Theoret. Comput. Sci., 746, 136-150, 2018.
  * [20] R. Incitti, The growth function of context-free languages, Theoret. Comput. Sci., 255, 601–605, 2001.
  * [21] E. Jeandel. Indécidabilité sur les automates quantiques. Master’s thesis. ENS Lyon, 2002.
  * [22] A. Kondacs, J. Watrous. On the power of quantum finite state automata. Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pp. 66–75, 1997.
  * [23] C. Moore, and J. Crutchfield. Quantum automata and quantum grammars. Theoret. Comput. Sci., 237, 275-306, 2000.
  * [24] M. Nivat. Transductions des langages de Chomsky. Ann. Inst. Fourier (Grenoble) 18, fasc. 1, 339-455, 1968.
  * [25] K. Nosan, A. Pouly, S. Schmitz, M. Shirmohammadi, and J. Worrell. On the computation of the Zariski closure of finitely generated groups of matrices, in Proceedings of ISSAC 2022, International Symposium on Symbolic and Algebraic Computation, ACM 2022, ISBN 978-1-4503-8688-3, pp. 129-138, 2022.
  * [26] A. Onishchik and E. Vinberg. Lie Groups and Algebraic Groups. Springer, Berlin, 1990.
  * [27] A. Paz. Introduction to Probabilistic Automata. Academic Press, New York, 1971.
  * [28] I. Potapov, P. Semukhin. Decidability of the Membership Problem for $2\times 2$ integer matrices, in Proceedings of SODA 2017 ACM-SIAM Symposium on Discrete Algorithms, SIAM 2017, ISBN 978-1-61197-478-2, pp. 170-186, 2017.
  * [29] A. Salomaa. On the index of context-free grammars and languages. Inf. and Control. 14, 474-477, 1969.
  * [30] J. S. Ullian. Partial Algorithm Problems for Context Free Languages. Inf. and Control. 11, 80-101, 1967.