\documentstyle{article} \newtheorem{theorem}[subsection]{Theorem} \newtheorem{definition}[subsection]{Definition} \newtheorem{notation}[subsection]{Notation} \newtheorem{proposition}[subsection]{Proposition} \newtheorem{lemma}[subsection]{Lemma} \newtheorem{remark}[subsection]{Remark} \newcommand\thmpar[1]{\begin{theorem}#1\end{theorem}} \newcommand\dfnpar[2]{\begin{definition}\bf({#1})\rm{#2}\end{definition}} \newcommand\notpar[1]{\begin{notation}\rm#1\end{notation}} \newcommand\proppar[1]{\begin{proposition}#1\end{proposition}} \newcommand\lempar[1]{\begin{lemma}#1\end{lemma}} \newcommand\rempar[1]{\begin{remark}\rm#1\end{remark}} \newcommand\prfpar[1]{\par\noindent{\bf Proof.}#1\hfill\rule{.3em}{1.5ex}} \newcommand\abspar[1]{\begin{quote}{\bf Abstract.}{#1}\end{quote}} \mathchardef\Sigma="0106 \newcommand\naka{\noindent\hfil} \newcommand\ma{\noindent\qquad\qquad} \newcommand\noi\noindent \newcommand\inters\cap \newcommand\union\cup \newcommand\trans[1]{\begin{array}[b]{@{\,}c@{\,}}#1\\[-1.5ex]\to\end{array}} \newcommand\transh[1]{\begin{array}[b]{@{\,}c@{\,}}#1\\[-1ex]\to\end{array}} \newcommand{\Union}[1]{\begin{array}[t]{@{}c@{}}\bigcup\\[-.8ex]\mbox{\scriptsize$#1$}\end{array}} \newcommand\SS{{\cal S}} \newcommand\Sum[1]{\begin{array}[t]{@{}c@{}}\sum\\[-.8ex]\mbox{\scriptsize$#1$}\end{array}} \newcommand\plng{{\mbox{\scriptsize\rm length}}} \newcommand\kuu{{\rm\O}} \newcommand\eps\epsilon \newcommand\bunsuu[2]{\begin{array}{@{}c@{}}#1\\\hline#2\end{array}} \newcommand\lng{{\mbox{\rm length}}} \newcommand\maru* \def\acc{\mathrel{\begin{array}[b]{@{}c@{}}*\;\\[-1.5ex]\to\end{array}}} \def\tate{\mathrel{|}} \newcommand\xref\ref \newcommand\xlabel\label \newcommand\vv\vspace %%% --- %%% --- %%% --- %%% --- %%% --- %%% \begin{document} \noindent{\Large\bf The measure of an omega regular language is \\ rational }\vspace{1.5ex} \noindent{\bf Takeuti Izumi } \noindent Graduate School of Informatics, Kyoto Univ. 606-8501, JAPAN. \\ {\tt takeuti@kuis.kyoto-u.ac.jp} \ \abspar { An omega regular language is the omega language which is recognised by a Buchi automaton. It has been known that the measure of an omega regular language recognised by a deterministic Buchi automaton is a rational number. This paper shows the measure of every omega regular language is a rational number. } \section{Introduction} An omega regular language is the omega language which is recognised by a Buchi automaton. Many studies on omega regular languages and Buchi automata appear in the literatures \cite{staiger,thomas}, which contain the proofs of most propositions in Sections 2 of this paper. An important property is that the recognising power of non-deterministic Buchi automata is properly stronger than that of deterministic Buchi automata. Yen Hsu-Chun and Lin Yih-Kai showed that the measure of an omega regular language recognised by a deterministic Buchi automaton is a rational number \cite{ly}. Unfortunately, their method cannot be applied to non-deterministic Buchi automata. Therefore, the characterisation on the general omega regular language remained open. The main result of this paper is that the measure of every omega regular language is a rational number. In order to prove this theorem, we will introduce two new notions, which are irreducibility and sparseness. The definition of irreducibility is the following: An omega regular language \(X\subset\Sigma^\omega\) is irreducible iff for each word \(v\in\Sigma^*\) there is a word \(w\in\Sigma^*\) such that \(x\in X\) iff \(v\cdot w\cdot x\in X\) for any \(x\in\Sigma^\omega\). The definition of sparseness is the following: An omega regular language \(X\) is sparse iff for a word \(w\in\Sigma^*\) and an irreducible set \(Y\subset\Sigma^\omega\), if it holds that \(x\in Y\) iff \(w\cdot x\in X\) for any \(x\in\Sigma^\omega\), then \(Y\) is empty. The purpose of these notions is to show the detachment lemma (\xref{detach}). The detachment lemma states that an omega regular language can be divided into a sparse set and some other subsets each of which are the concatenation of a finite regular language and an irreducible set. We will show some other lemmata on the measures. Lemma \xref{irr-m} states that the measure of an irreducible set is 1 or 0. Lemma \xref{sparse} states that the measure of a sparse set is 0. These three lemmata are crucial. And then, we will show the lemma such that the measure of each finite-state set is a rational number. The main lemma is proved with these lemmata above and the theorem by Lin and Yen. Our main result is an immediate consequence of this main lemma, for an omega regular language is finite-state. \section{Buchi Automaton} \dfnpar{Buchi Automaton} { A {\em Buchi automaton} is defined by five components \((\Sigma,S,T,s_0,F)\), where each component has the following meaning:% zzz \vv{1ex} \naka \begin{tabular}{l@{ }l} \(\Sigma\) & : alphabet, the set of symbols \\ \(S\) & : the set of states \\ \(T\subset S\times\Sigma\times S\) & : transition relation \\ \(s_0\in S\) & : the initial state \\ \(F\) & : the set of final states \end{tabular} % \vv{2ex} \noi Actually, final states are not final, but are to be visited infinitely many times. We call them final states only because of the traditional reason. Let \(B\) be a Buchi automaton such as \(B=(\Sigma,S,T,s_0,F)\). Then \(L(B)\) is a subset of \(\Sigma^\omega\) which defined as the following. For \((\sigma_1,\sigma_2,...)\in\Sigma^\omega\), \( (\sigma_1,\sigma_2,...)\in L(B) \) iff there is \((s_1,s_2,...)\in S^\omega\) such that \((s_{i-1},\sigma_i,s_i)\in T\) for each \(i=1,2,...\), and that there are infinitely many \(i\)'s such that \(s_i\in F\). %The set \(L(B)\) is called the {\em language} of \(B\). We say that the Buchi automaton \(B\) {\em recognises} the set \(L(B)\) } \dfnpar{Regularity} { A set \(X\subset\Sigma^\omega\) is {\em regular} iff \(X=L(B)\) for some Buchi automaton \(B\). } \notpar { A subset of \(\Sigma^\omega\) is called an {\em omega language}, and a regular subset of \(\Sigma^\omega\) is called an {\em omega regular language}. However, we call a omega language a set. Thus, an omega regular language is called a regular set. Note that what is called a set not always an omega language. } \rempar { We call a subset of \(\Sigma^*\) a {\em language}. We use the notion of {\em regular languages} as the ordinal definition, which is defined with ordinal finite automata. } \proppar {{\bf(Buchi '60)}\xlabel{reg-fsd} A regular set is an \(F\sigma\delta\)-set. } \prfpar { By Buchi \cite{buchi}, or also by Remark 3.4 on Page 354 in the literature \cite{staiger}. } \proppar {\xlabel{reg-det} If \(W\subset\Sigma^*\) is a regular language. Then \(W\cdot\Sigma^\omega\) is recognised by a deterministic Buchi automaton. } \prfpar { By Proposition 3.4 on Page 355 with Theorem 3.1 on Page 354 in the literature \cite{staiger}. } \notpar { For \(w=(w_1,w_2,...,w_m)\in\Sigma^*\) and \(x=(x_1,x_2,...,x_n)\in\Sigma^*\) or \(X=(x_1,x_2,...) \) \( % zzz a4 12pt \in\Sigma^\omega\), we write \(w\cdot x\) or \(wx\) for the concatenation of \(w\) and \(x\) which is \((w_1,...,w_m,x_1,...x_n)\) or \((w_1,...,w_m,x_1,...)\). For a set \(X\subset\Sigma^\omega\), \(w\cdot X=\{w\cdot x\tate x\in X\}\). For sets \(W\subset\Sigma^*\) and \(X\subset\Sigma^\omega\), \(W\cdot X=\{w\cdot X\tate w\in W\}\). } \dfnpar{States} { For \(X\subset\Sigma^\omega\) and \(w\in\Sigma^*\), we write \(X/w\) for \(\{x\in\Sigma^\omega\tate w\cdot x\in X\}\), and \(\SS(X)\) for \(\{Y\subset\Sigma^\omega\tate w\in\Sigma^*,Y=X/w\}\). We call a set in \(\SS(X)\) {\em States}. } \rempar { \((X-Y)/w=X/w-Y/w\) } \dfnpar{Finite-state sets} { A set \(X\subset\Sigma^\omega\) is {\em finite-state} iff \(\SS(X)\) is finite. } \proppar {\xlabel{finite} Each regular set is finite-state. } \prfpar { In \cite{thomas}. } \proppar {\xlabel{regular} For a finite-state set \(X\subset\Sigma^\omega\) and a set \(Y\subset\Sigma^\omega\), the set of words \(\{w\in\Sigma^*\tate X/w=Y\}\) is a regular language. } \prfpar{ Easy. } \section{Irreducible set} \dfnpar{Accessibility} { For \(X,Y\in\Sigma^\omega\), the relation \(X\acc Y\) holds iff \(Y\in\SS(X)\), that is, there is \(w\in\Sigma^*\) such that \(Y=X/w\). This relation \(\acc\) is called {\em accessibility}. %We say that \(Y\) is {\em accessible} from \(X\) when \(X\acc Y\). } \rempar {\xlabel{preorder} Accessibility is reflexive and transitive. } \proppar {\xlabel{maximal} Let \(D\) be a non-empty finite set, and a relation \(\leq\) be preorder, that is, a reflexive transitive relation. Then, for each \(d\in D\) there is a maximal element \(e\) in \(D\) with respect to the preorder \(\leq\) such that \(d\leq e\). } \prfpar { Induction on the number of the elements of \(D\). } \dfnpar{Irreducibility} { A finite-state set \(X\in\Sigma^\omega\) is {\em irreducible} iff \(Y\acc X\) for each \(Y\in\SS(X)\) } \proppar {\xlabel{irr-ex} For a finite-state set \(X\subset\Sigma^\omega\), there exists at least one irreducible set in \(\SS(X)\). } \prfpar { An irreducible set is a maximal element with respect to \(\acc\), and the domain \(\SS(X)\) is non-empty and finite. Hence, it exists by Proposition \xref{maximal}. } \dfnpar{Sparseness} { A finite-state set \(X\) is {\em sparse} iff the only irreducible set in \(\SS(X)\) is \(\O\). } \rempar { There are non-empty sparse sets. For example, a singleton \(\{0^\omega\}\) is sparse where \(\Sigma=\{0,1\}\). } \dfnpar{\(\maru\)-operation} { For sets \(X,Y\subset\Sigma^\omega\), the set \(X\maru Y\in\Sigma^\omega\) is defined as: \noi\ \( X \maru Y = \{ w \cdot x \in X \tate \exists v \in \Sigma^*. \; x \in X/w=Y/v \} =\union\{w\cdot(X/w)\tate X/w\in\SS(Y)\} \). } \rempar {\xlabel{pref} Let \(X\) and \(Y\) be subsets of \(\Sigma^\omega\). Put \(W=\{w\in\Sigma^*\tate X/w\in\SS(Y)\}\). Then, there is a prefix-free subset \(V\subset W\) such that for each \(w\in W\) there are \(v\in V\) and \(u\in\Sigma^*\) such that \(v\cdot u=w\). Thus it holds that \( X \maru Y = \Union{v\in V} v\cdot(X/v) \) } \rempar {\xlabel{pref-reg} In general, for each \(W\subset\Sigma^*\) there is a prefix-free subset \(V\subset W\) such that for each \(w\in W\) there are \(v\in V\) and \(u\in\Sigma^*\) such that \(v\cdot u=w\). If \(W\) is a regular language, then so is \(V\). } \proppar {\xlabel{aster} For sets \(X,Y\in\Sigma^\omega\) and a word \(w\in\Sigma^*\), %\par\naka % zzz \((X/w)\maru Y=(X\maru Y)/w\). } \prfpar { For \(x\in\Sigma^\omega\), \(x\in(X\maru Y)/w\) iff \(wx\in X\maru Y\), which is equivalent to \naka\( \exists u,v\in\Sigma^*.\exists y\in\Sigma^\omega.\;wx=uy\;\&\;y\in X/u=Y/v \). \noi This is equivalent to \ma\( \exists u,u',v\in\Sigma^*.\exists y\in\Sigma^\omega.\; u=wu'\;\&\;x=u'y\;\&\;y\in X/wu'=Y/v \) \ma or \ma\( \exists u,w',v\in\Sigma^*.\exists y\in\Sigma^\omega.\; w=uw'\;\&\;w'x=y\;\&\;y\in X/u=Y/v \) The upper case is transformed by deleting the variable \(u\), then it is equivalent to: \naka \(\exists u',v\in\Sigma^*.\exists y\in\Sigma^\omega.\;x=u'y\;\&\;y\in X/wu'=Y/v\). We consider the lower case. Suppose that \(w=uw'\;\&\;w'x=y\;\&\;y\in X/u=Y/v\). Then \(x\in X/uw'=X/w=Y/vw'\). This implies \naka\( \exists u',v'\in\Sigma^*.\exists y'\in\Sigma^\omega.\;x=u'y'\;\&\;y'\in X/wu'=Y/v'\). \noi by instantiating \(u'\) with empty word, \(v'\) with \(vu'\), and \(y'\) with \(x\). In the formula with disjunction, the right part of disjunction implies the left part. Hence, the whole formula is equivalent to the left part. Thus it is equivalent to: \naka\( \exists u,v\in\Sigma^*.\exists y\in\Sigma^\omega.\;x=uy\;\&\;y\in X/wu=Y/v\). \noi This is equivalent to \naka\( \exists u,v\in\Sigma^*.\exists y\in\Sigma^\omega.\;x=uy\;\&\;y\in(X/w)/u=Y/v \). \noi This is equivalent to \(x\in(X/w)\maru Y\). } \lempar {{\bf(Detachment lemma)}\xlabel{detach} For each finite-state set \(X\), there are a sparse set \(Z\), a finite index set \(I\) and indexed families \(\{W_i\}_{i\in I}\) and \(\{Y_i\}_{i\in I}\) such that %\vv{1ex} \naka \( X = Z \union \Union{i\in I} W_i\cdot Y_i \) %\vv{1ex} \noi where each \(W_i\) is a prefix-free regular language, each \(Y_i\) is an irreducible set, and \( W_i\cdot Y_i \inters W_j\cdot Y_j = \kuu \) and \( Z \inters W_j\cdot Y_j = \kuu \) for any \(i\neq j\). } \prfpar { The proof is done by induction on the number of the elements of \(\SS(X)-\{\O\}\). (Base case) If \(\SS(X)-\{\O\}=\O\), then \(X=\O\) and the assertion of this lemma holds. (Induction step) We show that the case of \(X\) can be reduced to the case of another \(X'\) where \(\SS(X')-\{\O\}\) has less elements than \(\SS(X)-\{\O\}\). By the Proposition \xref{irr-ex}, there is at least one irreducible set in \(\SS(X)\). If the only irreducible set in \(\SS(X)\) is the empty set, then \(X\) is sparse, and the assertion of the lemma holds. Therefore we assume that there are non-empty irreducible set \(Y\in\SS(X)\). Put \(Y\in\SS(X)\) as such an irreducible set. Each \(Z\in\SS(Y)\) is also irreducible by the definition of irreducibility. If \(\SS(X)=\SS(Y)\), then \(X\) is already irreducible, and the assertion of the lemma holds, because \(X=\O\union\{()\}\cdot X\) where \(\O\) is sparse and the set \(\{()\}\) is the singleton of empty words, which is a regular language. Therefore, we assume that \(\SS(X)\neq\SS(Y)\), that is, \(X\not\in\SS(Y)\). First we will show that \(X\maru Y=\Union{i\in I}W_i\cdot Y_i\) and it holds that for each \(i\in I\) the set \(W_i\) is a prefix-free regular language, and \(Y_i\in\SS(Y)\). Let \(I\) be a index set which has the same number of elements as \(\SS(Y)\) has, and \(\{Y_i\tate i\in I\}\) be equal to \(\SS(Y)\). Put \(V_i=\{v\in\Sigma^*\tate X/v=Y_i\}\). Then \(X\maru Y=\Union{i\in I}V_i\cdot Y_i=\Union{i\in I}\,\Union{v\in V_i}v\cdot(X/v)\). As Remark \xref{pref}, there is a prefix-free subset \(W\subset\Union{i\in I}V_i\) such that \(X\maru Y=\Union{w\in W}w\cdot(X/w)\). Put \(W_i=W\inters V_i\). Then \(W_i\) is prefix-free. As Proposition \xref{regular}, each \(V_i\) is a regular language, then so is \(\Union{i\in I}V_i\), for \(I\) is finite. As Remark \xref{pref-reg}, the subset \(W\) is a regular language, and then so is \(W_i\). Therefore we have \(X\maru Y=\Union{i\in I}W_i\cdot Y_i\) where for each \(i\in I\), \(W_i\) is a prefix-free regular language and \(Y_i\in\SS(Y)\). Moreover, each \(V_i\) and \(V_j\) are disjoint for \(i\neq j\). Therefore each \(W_i\) and \(W_j\) are disjoint. In addition, \(W_i\union W_j\) is prefix-free. These facts imply that each \(W_i\cdot Y_i\) and \(W_j\cdot Y_j\) are disjoint. Next we discuss \(X-X\maru Y\). The mapping \(Z\mapsto Z-Z\maru Y\) is a function of \(\SS(X)\) into \(\SS(X-X\maru Y)\). That is because if \(Z\in\SS(X)\) then \(Z=X/w\) for some \(w\). Hence \(Z\maru Y=(X\maru Y)/w\) by Proposition \xref{aster}, so \(Z-Z\maru Y=X/w-(X\maru Y)/w=(X-X\maru Y)/w\in\SS(X-X\maru Y)\). Moreover, the mapping \(Z\mapsto Z-Z\maru Y\) is a surjection. That is because if \(Z'\in\SS(X-X\maru Y)\) then for some \(w\), it holds that \(Z'=(X-X\maru Y)/w=(X/w)-(X/w)\maru Y\) and \(X/w\in\SS(X)\). Note that this mapping maps \(Y\) into \(Y-Y\maru Y=\O\), and of cause \(\O-\O\maru Y=\O\). Hence, the number of elements of \(\SS(X-X\maru Y)-\{\O\}\) is less than or equal to that of \(\SS(X)-\{\O,Y\}\), Therefore the number of elements of \(\SS(X-X\maru Y)-\{\O\}\) is less than that of \(\SS(X)-\{\O\}\). Thus, induction hypothesis holds for \(\SS(X-X\maru Y)\). By the induction hypothesis, there are a sparse set \(Z\) and familys \(\{W'_i\}_{i\in I'}\) and \(\{Y'_i\}_{i\in I'}\) such that \( X - X \maru Y = Z \union \Union{i\in I'} W'_i\cdot Y'_i \) where \(Z\), \(\{W'_i\}={i\in I'}\) and \(\{Y'_i\}={i\in I'}\) satisfies the disjointness in the assertion of this lemma. Therefore \naka\( X = X \maru Y \union ( X - X \maru Y ) = Z \union \left( \Union{i\in I'} W'_i\cdot Y'_i \right) \union \left( \Union{i\in I} W_i\cdot Y_i \right) \) \vv{1ex} \noi The disjointness in the assertion holds because \( X \maru Y \) and \( X - X \maru Y \) are disjoint. \par\ % zzz } \section{Measure} \rempar { We fix the alphabet \(\Sigma\) which consists of \(n\) symbols. } \notpar { We use the notations \(U\) and \(U(w)\) as \(U=\Sigma^\omega\) and \(U(w)=w\cdot\Sigma^\omega\subset\Sigma^\omega\) for \(w\in\Sigma^*\). } \dfnpar{Measure} { For a set \(X\subset\Sigma^\omega\), the measure \(\mu(X)\) is defined as: %\vv{1ex} \naka \( \mu(X)=\inf\left\{\Sum{i\in I}n^{-\plng(w_i)}\left| X\subset\Union{i\in I}U(w_i)\right.\right\} \). } \dfnpar{Measurability} { A set \(X\subset\Sigma^\omega\) is {\em measurable} iff \(\mu(X)+\mu(U-X)=1\). } \rempar { This \(\mu(X)\) is usually called the outer measure if \(X\) is not neasurable. } \rempar { The following propositions \xref{m-fsd} and \xref{m-pref} are easily seen form the discussion in the literature \cite{textbook}. } \proppar {\xlabel{m-fsd} If \(X\subset U\) is a \(F\sigma\delta\)-set, then \(X\) is measurable. } \proppar {\xlabel{m-pref} If the set of words \(\{w_i\in\Sigma^*\tate i\in I\}\) is prefix-free, Then, it holds that \naka \(\mu\left(\Union{i\in I}w_i\cdot X_i\right) =\Sum{i\in I}2^{-\plng(w_i)}\mu(X_i)\). } \lempar { A regular set is measurable. } \prfpar { By Propositions \xref{reg-fsd} and \xref{m-fsd}. } \thmpar {{\bf(Lin \& Yen '00)}\xlabel{m-det} For each deterministic Buchi automaton \(B\), the measure \(\mu(L(B))\) is rational. } \prfpar { By Lin and Yen \cite{ly}. } \rempar { Lin and Yen proves the theorem above with the property of Markov chains. A deterministic Buchi automaton is regarded as a Markov chain in their proof. Unfortunately, their method cannot be applied to non-deterministic Buchi automata. } \lempar {\xlabel{irr-eq} If \(X\) is irreducible, then for each \(Y\in\SS(X)\), \(\mu(X)=\mu(Y)\). } \prfpar { Because \(\SS(X)\) is finite, then there exists \(m=\max\{\mu(Y)\tate Y\in\SS(X)\}\). Put \(E=\{Y\in\SS(X)\tate\mu(Y)=m\}\). Then the assertion of this lemma is equivalent to \(E=\SS(X)\). We will prove this by reductio ad absurdum. Suppose that \(\SS(X)-E\) is not empty. Put \(Y\) and \(Y'\) as \(Y\in E\) and \(Y'\in\SS(X)-E\). Because \(X\) is irreducible, there is a sequence of sets \(Y=Y_1,Y_2,..., %\) \( % zzz Y_{l-1},Y_l=Y'\) such that \(Y_i/\sigma_i=Y_{i+1}\) for some \(\sigma_i\in\Sigma\). Because \(Y_1\in E\) and \(Y_l\not\in E\), there is a pair \((Y_i,Y_{i+1})\) such that \(Y_i\in E\) and \(Y_{i+1}\not\in E\). Note that \naka \(Y_i=\Union{\sigma\in\Sigma}\sigma\cdot(Y_i/\sigma)\). \noi By Proposition \xref{m-pref}, \naka \(\mu(Y_i)=\bunsuu1n\Sum{\ \sigma\in\Sigma\ }\mu(Y_i/\sigma)\) \noi Therefore, \naka \(m\leq\bunsuu1n\;\mu(Y_{i+1})+\bunsuu{n-1}n\;m<\bunsuu1n\;m+\bunsuu{n-1}n\;m=m\), \noi that is, \( m\bunsuu\eps{1-m}\). Let \(K\) be the set \(\{v\in\Sigma^l\tate U(v)\not\subset V\}\). Then \(\Union{v\in K}U(v)=U-V\). The number of all the elements of \(K\) is \(n^l(1-b)\). Thus, the following equations hold: \vv{1ex} \naka \(X-V=X\union\left(\Union{v\in K}U(v)\right)=\Union{v\in K}X\inters U(v) =\Union{v\in K}v\cdot(X/v)\). \vv{1ex} \noi By Lemma \xref{irr-eq}, \(\mu(X/v)=m\), hence by Proposition \xref{m-pref}, \vv{1ex} \naka \(\mu(X-V)=\Sum{v\in K}n^{-l}\mu(X/v)=(1-b)\cdot m\). %\vv{1ex} \noi Therefore, \vv{1ex} \naka \(\mu(X\union V)=\mu(V)+\mu(X-V)=b+m(1-b)=m+b(1-m)>m+\eps\). \vv{1ex} On the other hand, \vv{1ex} \naka \(X\subset\Union{i\in I}U(w_i)\) \ and \ \(V\subset\Union{i\in I}U(w_i)\). \noi Thus \naka \(X\union V\subset\Union{i\in I}U(w_i)\). \noi Therefore \naka \(\mu(X\union V)\leq\mu\left(\Union{i\in I}U(w_i)\right)