Dissecting Power of a Finite Intersection of Context Free Languages


Abstract

Let \(\exp^{k,\alpha}\)​ denote a tetration function defined as follows: \(\exp^{1,\alpha}=2^{\alpha}\)​ and \(\exp^{k+1,\alpha}=2^{\exp^{k,\alpha}}\)​, where \(k,\alpha\)​ are positive integers. Let \(\mathop{\mathrm{\Delta}}_n\)​ denote an alphabet with \(n\)​ letters. If \(L\subseteq\mathop{\mathrm{\Delta}}_n^*\)​ is an infinite language such that for each \(u\in L\)​ there is \(v\in L\)​ with \(\vert v\vert\leq \exp^{k,\alpha}\vert u\vert\)​ then we call \(L\)​ a language with the growth bounded by \((k,\alpha)\)​-tetration.

Given two infinite languages \(L_1,L_2\in \mathop{\mathrm{\Delta}}_n^*\)​, we say that \(L_1\)dissects \(L_2\)​ if \(\vert L_1\cap L_2\vert=\infty\)​ and \(\vert(\mathop{\mathrm{\Delta}}_n^*\setminus L_1)\cap L_2\vert=\infty\)​.

Let \(L\subseteq\mathop{\mathrm{\Delta}}_n^*\)​ be an infinite language with the growth bounded by \((k,\alpha)\)​-tetration, where \(k\geq 2\)​. We show that there are \(3k-3\)​ context free languages \(L_1,L_2,\dots,L_{3k-3}\)​ over the alphabet \(\mathop{\mathrm{\Sigma}}_{2k-1}\)​ with \(2k-1\)​ letters, an erasing alphabetical homomorphism \(\upsilon: \mathop{\mathrm{\Sigma}}_{2k-1}^*\rightarrow \mathop{\mathrm{\Delta}}_1^*\)​, a nonerasing alphabetical homomorphism \(\pi: \mathop{\mathrm{\Delta}}_n^*\rightarrow \mathop{\mathrm{\Delta}}_1^*\)​ such that the homomorphic image \(\upsilon(\bigcap_{i=1}^{3k-3}L_i)\)​ dissects the homomorphic image \(\pi(L)\)​.

1 Introduction

In the theory of formal languages, the regular and the context free languages constitute a fundamental concept that attracted a lot of attention in the past several decades. Recall that every regular language is accepted by some deterministic finite automaton and every context free language is accepted by some pushdown automaton.

In contrast to regular languages, the context free languages are closed neither under intersection nor under complement. The intersection of context free languages have been systematically studied in [1]–[5]. Let \(\mathop{\mathrm{CFL}}_{k}\)​ denote the family of all languages such that for each \(L\in \mathop{\mathrm{CFL}}_k\)​ there are \(k\)​ context free languages \(L_1, L_2,\dots,L_k\)​ with \(L=\bigcap_{i=1}^kL_i\)​. For each \(k\)​, it has been shown that there is a language \(L\in\mathop{\mathrm{CFL}}_{k+1}\)​ such that \(L\not \in \mathop{\mathrm{CFL}}_{k}\)​. Thus the \(k\)​-intersections of context free languages form an infinite hierarchy in the family of all formal languages lying between context free and context sensitive languages [2].

One of the topics in the theory of formal languages that has been studied is the dissection of infinite languages. Let \(\mathop{\mathrm{\Delta}}_n\)​ be an alphabet with \(n\)​ letters, and let \(L_1,L_2\subseteq \mathop{\mathrm{\Delta}}_n^*\)​ be infinite languages. We say that \(L_1\)dissects \(L_2\)​ if \(\vert L_1\cap L_2\vert=\infty\)​ and \(\vert(\mathop{\mathrm{\Delta}}_n^*\setminus L_1)\cap L_2\vert=\infty\)​. Let \(\mathbb{C}\)​ be family of languages. We say that a language \(L_1\in \mathop{\mathrm{\Delta}}_n^*\)​ is \(\mathbb{C}\)​-dissectible if there is a \(L_2\in \mathbb{C}\)​ such that \(L_2\)​ dissects \(L_1\)​. Let \(REG\)​ denote the family of regular languages. In [6] the \(REG\)​-dissectibility has been investigated. Several families of \(REG\)​-dissectible languages have been presented. Moreover it has been shown that there are infinite languages that cannot be dissected with a regular language. Also some open questions for \(REG\)​-dissectibility can be found in [6]. For example it is not known if the complement of a context free languages is \(REG\)​-dissectible.

There is a related longstanding open question in [7]: Given two context free languages \(L_1,L_2\subseteq \mathop{\mathrm{\Delta}}_n^*\)​ such that \(L_1\subset L_2\)​ and \(L_2\setminus L_1\)​ is an infinite set, is there a context free language \(L_3\)​ such that \(L_3\subset L_2\)​, \(L_1\subset L_3\)​, and both the languages \(L_3\setminus L_1\)​ and \(L_2\setminus L_3\)​ are infinite? This question was mentioned also in [6].

Some other results concerning the dissection of infinite languages may be found in [8]. A similar topic is the finding of minimal covers of languages; see [9]. Recall that a language \(L_1\subseteq\mathop{\mathrm{\Delta}}_n^*\)​ is called \(\mathbb{C}\)​-immune if there is no infinite language \(L_2\subseteq L_1\)​ such that \(L_2\in \mathbb{C}\)​. The immunity is also related to the dissection of languages; some results on this theme can be found in [5], [10], [11].

Let \(\mathbb{N}\)​ denote the set of all positive integers. An infinite language \(L\subseteq \mathop{\mathrm{\Delta}}_n^*\)​ is called constantly growing, if there is a constant \(c_0\in \mathbb{N}\)​ and a finite set \(K\subset\mathbb{N}\)​ such that for each \(w\in L\)​ with \(\vert w\vert\geq c_0\)​ there is a word \(\bar w\in L\)​ and a constant \(c\in K\)​ such that \(\vert \bar w\vert=\vert w\vert+c\)​. We say also that \(L\)​ is \((c_0,K)\)​-constantly growing. In [6], it has been proved that every constantly growing language \(L\)​ is \(REG\)​-dissectible.

We define a tetration function (a repeated exponentiation) as follows: \(\exp^{1,\alpha}=2^{\alpha}\)​ and \(\exp^{j+1,\alpha}=2^{\exp^{j,\alpha}}\)​, where \(j\in \mathbb{N}\)​. The tetration function is known as a fast growing function. If \(k,\alpha\)​ are positive positive integers and \(L\subseteq\mathop{\mathrm{\Delta}}_n^*\)​ is an infinite language such that for each \(u\in L\)​ there is \(v\in L\)​ with \(\vert v\vert\leq \exp^{k,\alpha}\vert u\vert\)​ then we call \(L\)​ a language with the growth bounded by \((k,\alpha)\)​-tetration.

Let \(L\subseteq\mathop{\mathrm{\Delta}}_n^*\)​ be an infinite language with the growth bounded by \((k,\alpha)\)​-tetration, where \(k\geq 2\)​. In the current article we show that there are:

  • an alphabet \(\mathop{\mathrm{\Sigma}}_{2k-1}\)​ with \(\vert \mathop{\mathrm{\Sigma}}_{2k-1}\vert=2k-1\)​,

  • an erasing alphabetical homomorphism \(\upsilon: \mathop{\mathrm{\Sigma}}_{2k-1}^*\rightarrow \mathop{\mathrm{\Delta}}_1^*\)​,

  • a nonerasing alphabetical homomorphism \(\pi: \mathop{\mathrm{\Delta}}_n^*\rightarrow \mathop{\mathrm{\Delta}}_1^*\)​, and

  • \(3k-3\)​ context free languages \(L_1,L_2,\dots,L_{3k-3}\subseteq \Sigma_{2k-1}^*\)

such that the homomorphic image \(\upsilon(\bigcap_{i=1}^{3k-3}L_i)\)​ dissects the homomorphic image \(\pi(L)\)​.

We sketch the basic ideas of our proof. Recall that a non-associative word on the letter \(z\)​ is a “well parenthesized” word containing a given number of occurrences of \(z\)​. It is known that the number of non-associative words containing \(n+1\)​ occurrences of \(z\)​ is equal to the \(n\)​-th Catalan number. For example for \(n=3\)​ we have \(5\)​ distinct non-associative words: \((((zz)z)z)\)​, \(((zz)(zz))\)​, \((z(z(zz)))\)​, \((z((zz)z))\)​, and \(((z(zz))z)\)​. Every non-associative word contains the prefix \((^kz\)​ for some \(k\in\mathbb{N}\)​, where \((^k\)​ denotes the \(k\)​-th power of the opening bracket. It is easy to verify that there are non-associative words such that \(k\)​ equals “approximately” \(\log_2{n}\)​. We construct three context free languages whose intersection accepts such words; we call these words balanced non-associative words. By counting the number of opening brackets of a balanced non-associative word with \(n\)​ occurrences of \(z\)​ we can compute a logarithm of \(n\)​.

Let \(\log_2^{(1)}{n}=\log_2{n}\)​ and \(\log_2^{(j+1)}{n}=\log_2^{(j)}{(\log_2{n})}\)​. Our construction can be “chained” so that we construct \(3k-3\)​ context free languages, whose intersection accepts words with \(n\)​ occurrences of \(z\)​ and a prefix \(x^j\bar z\)​, where \(j\)​ is equal “approximately” to \(\log_2^{(k)}{n}\)​ and \(\bar z\not=x\)​. If \(L\)​ is a language with the growth bounded by a \((k,\alpha)\)​-tetration then the language \(\bar L=\{z^j\mid j=\lceil\log_2^{(k)}{\vert w\vert}\rceil\mbox{ and }w\in L\}\)​ is constantly growing. Less formally said, by means of intersection of \(3k-3\)​ context free languages we transform the challenge of dissecting a language with the growth bounded by \((k,\alpha)\)​-tetration to the challenge of dissecting a constantly growing language. This approach allows us to prove our result.

2 Preliminaries

Let \(\mathbb{R}^+\)​ denote the set of all positive real numbers.

Let \(\mathop{\mathrm{B}}_k=\{x_1,x_2,\dots,x_k\}\)​ be an ordered alphabet (set) of \(k\)​ distinct opening brackets, and let \(\bar \mathop{\mathrm{B}}_k=\{y_1,y_2, \dots, y_k\}\)​ be an ordered alphabet (set) of \(k\)​ distinct closing brackets. We define the alphabet \(\mathop{\mathrm{\Sigma}}_{2k-1}=\mathop{\mathrm{B}}_k\cup(\bar\mathop{\mathrm{B}}_k\setminus\{y_1)\})\)​. The alphabet \(\mathop{\mathrm{\Sigma}}_{2k-1}\)​ contains all opening brackets \(\mathop{\mathrm{B}}_k\)​ and all the closing brackets without the the first one \(\bar \mathop{\mathrm{B}}_k\setminus\{y_1\}\)​. It follows that \(\vert \mathop{\mathrm{\Sigma}}_{2k-1}\vert=2k-1\)​.

Let \(\epsilon\)​ denote the empty word. Given a finite alphabet \(S\)​, let \(S^+\)​ denote the set of all finite nonempty words over the alphabet \(S\)​ and let \(S^*=S^+\cup\{\epsilon\}\)​.

Given a finite alphabet \(S\)​, let \(\mathop{\mathrm{occur}}(w,t)\)​ denote the number of occurrences of the nonempty factor \(t\in S^+\)​ in the word \(w\in S^*\)​. Let \(\mathop{\mathrm{Fac}}(w)\)​ denote the set of all factors a word \(w\in S^*\)​. We define that \(\epsilon,w\in\mathop{\mathrm{Fac}}(w)\)​; i.e. the empty word and the word \(w\)​ are factors of \(w\)​. Let \(\mathop{\mathrm{Pref}}(w)\subseteq \mathop{\mathrm{Fac}}(w)\)​ denote the set of all prefixes of \(w\in S^*\)​. We define that \(\epsilon,w\in \mathop{\mathrm{Pref}}(w)\)​. Let \(\mathop{\mathrm{Suf}}(w)\subseteq \mathop{\mathrm{Fac}}(w)\)​ denote the set of all suffixes of \(w\in S^*\)​. We define that \(\epsilon,w\in \mathop{\mathrm{Suf}}(w)\)​.

Given two finite alphabets \(S_1,S_2\)​, a homomorphism from \(S_1^*\)​ to \(S_2^*\)​ is a function \(\tau:S_1^*\rightarrow S_2^*\)​ such \(\tau(ab)=\tau(a)\tau(b)\)​, where \(a,b\in S_1^+\)​. It follows that in order to define a homomorphism \(\tau\)​, it suffices to define \(\tau(z)\)​ for every \(z\in S_1\)​; such definition “naturally” extends to every word \(a\in S_1^+\)​. We say that \(\tau\)​ is an nonerasing alphabetical homomorphism if \(\tau(z)\in S_2\)​ for every \(z\in S_1\)​. We say that \(\tau\)​ is an erasing alphabetical homomorphism if \(\tau(z)\in S_2\cup\{\epsilon\}\)​ for every \(z\in S_1\)​ and there is at least one \(z\in S_1\)​ such that \(\tau(z)=\epsilon\)​.

3 Balanced non-associative words

Suppose \(k,m\in \mathbb{N}\)​, where \(k,m\geq 2\)​, and \(k\geq m\)​. To simplify the notation we define \(x=x_m\)​, \(y=y_m\)​, and \(z=x_{m-1}\)​; it means that \(x\)​ denotes the \(m\)​-th opening bracket, \(y\)​ denotes the \(m\)​-th closing bracket, and \(z\)​ denotes the \(m-1\)​-th opening bracket.

Let \(\mu_{k,m}: \mathop{\mathrm{\Sigma}}_{2k-1}^*\rightarrow \mathop{\mathrm{\Sigma}}_{2k-1}^*\)​ be an erasing alphabetical homomorphism defined as follows:

  • \(\mu_{k,m}(z)=z\)​,

  • \(\mu_{k,m}(x)=x\)​,

  • \(\mu_{k,m}(y)=y\)​.

  • \(\mu_{k,m}(a)=\epsilon\)​, where \(a\in \mathop{\mathrm{\Sigma}}_{2k-1}\setminus\{x,y,z\}\)​.

Let \(L\subseteq \mathop{\mathrm{\Sigma}}_{2k-1}^*\)​ be a language, we define the language \(\mu_{k,m}(L)=\{\mu_{k,m}(w)\mid w\in L\}\)​.

For given \(k,m\)​ the erasing alphabetical homomorphism \(\mu_{k,m}\)​ sends all opening and closing brackets from \(\mathop{\mathrm{B}}_k\)​ and \(\bar \mathop{\mathrm{B}}_k\)​ to the empty string with the exception of \(x\)​, \(y\)​, and \(z\)​.

Let \(\mathop{\mathrm{Naw}}_{k,m}\subseteq \mathop{\mathrm{\Sigma}}_{2k-1}^*\)​ be the context free language generated by the following context free grammar, where \(S\)​ is a start non-terminal symbol, \(N\)​ is a non-terminal symbol, and \(x,y,z,a\)​ are terminal symbols (the letters from \(\mathop{\mathrm{\Sigma}}_{2k-1}\)​).

  • \(\mathop{\mathrm{S}}\rightarrow \mathop{\mathrm{N}}x\mathop{\mathrm{N}}\mathop{\mathrm{S}}\mathop{\mathrm{S}}\mathop{\mathrm{N}}y\mathop{\mathrm{N}}\mid \mathop{\mathrm{N}}x\mathop{\mathrm{N}}z\mathop{\mathrm{N}}y\mathop{\mathrm{N}}\mid \mathop{\mathrm{N}}x\mathop{\mathrm{N}}z\mathop{\mathrm{N}}z\mathop{\mathrm{N}}y\mathop{\mathrm{N}}\)​,

  • \(\mathop{\mathrm{N}}\rightarrow a\mathop{\mathrm{N}}\mid \epsilon\)​, where \(a\in \mathop{\mathrm{\Sigma}}_{2k-1}\setminus\{x,y,z\}\)​.

We call the words from \(\mathop{\mathrm{Naw}}_{k,m}\)non-associative words over the opening bracket \(x\)​, the closing bracket \(y\)​, and the letter \(z\)​.

Let \(M=\mu_{k,m}(\mathop{\mathrm{Naw}}_{k,m})\)​. To understand the definition of \(\mathop{\mathrm{Naw}}_{k,m}\)​, note that the language \(M\)​ is generated by the context free grammar defined by: \(\mathop{\mathrm{S}}\rightarrow x\mathop{\mathrm{S}}\mathop{\mathrm{S}}y\mid xzy\mid xzzy\mbox{.}\)​ To see this, just remove the non-terminal symbol \(N\)​ in the definition of \(\mathop{\mathrm{Naw}}_{k,m}\)​. The usage of the non-terminal symbol \(\mathop{\mathrm{N}}\)​ allows to “insert” between any two letters of a word from \(\mu_{k,m}(\mathop{\mathrm{Naw}}_{k,m})\)​ the words from \(K=(\mathop{\mathrm{\Sigma}}_{2k-1}\setminus\{x,y,z\})^*\)​; the set \(K\)​ contains words from \(\mathop{\mathrm{\Sigma}}_{2k-1}^*\)​ that have no occurrence of \(x,y,z\)​. It means that if \(w=w_1w_2\dots w_n\in \mu_{k,m}(\mathop{\mathrm{Naw}}_{k,m})\)​, then \(t_0w_1t_1w_2t_2\dots t_{n-1}w_nt_n\in \mathop{\mathrm{Naw}}_{k,m}\)​, where \(w_i\in \{x,y,z\}\)​ and \(t_i\in K\)​.

The reason for the name “non-associative words” is the obvious similarity between the words from \(M\)​ and the “standard non-associative words” mentioned in the introduction section. For our purpose it is necessary that \(w_1xzyw_2\in M\)​ if and only if \(w_1xzzyw_2\in M\)​ for every \(w_1,w_2\in \{x,z,y\}^*\)​.

Recall that a pushdown automaton is a \(6\)​-tuple \((\mathop{\mathrm{Q}},\mathop{\mathrm{\Delta}}, \Gamma, q_0, \mathop{\mathrm{S}},\delta)\)​, where

  • \(\mathop{\mathrm{Q}}\)​ is a set of states,

  • \(\mathop{\mathrm{\Delta}}\)​ is an input alphabet,

  • \(\Gamma\)​ is a stack alphabet,

  • \(q_0\in \mathop{\mathrm{Q}}\)​ is an input state,

  • \(\mathop{\mathrm{S}}\in \Gamma\)​ is the initial symbol of the stack,

  • \(\delta: (\mathop{\mathrm{Q}}\times \mathop{\mathrm{\Delta}}\times \Gamma)\rightarrow (\mathop{\mathrm{Q}},\Gamma^*)\)​ is a transition function.

We define that a pushdown automaton accepts a word by the empty stack, hence we do not need to define the set of final states. Given a pushdown automaton \(g\)​, let \(\mathop{\mathrm{AL}}(g)\subseteq \mathop{\mathrm{\Delta}}^*\)​ denotes the language accepted by \(g\)​. Let \(\Lambda_{k,m}=\mathop{\mathrm{AL}}(g_{k,m})\subseteq\mathop{\mathrm{\Sigma}}_{2k-1}^*\)​ denote the language accepted by the pushdown automaton \(g_{k,m}=(\mathop{\mathrm{Q}},\mathop{\mathrm{\Sigma}}_{2k-1}, \Gamma, q_S, \mathop{\mathrm{S}},\mathop{\mathrm{F}},\delta)\)​, where:

  • \(\mathop{\mathrm{Q}}=\{q_{S},q_{B}, q_0, q_x,q_r\}\)​,

  • \(\Gamma=\{\mathop{\mathrm{S}}, X\}\)​,

  • \(\delta(q,a,u)\rightarrow(q,u)\)​, where \(q\in \mathop{\mathrm{Q}}\)​, \(u\in\Gamma\)​, and \(a\in \mathop{\mathrm{\Sigma}}_{2k-1}\setminus\{x,y,z\}\)​,

  • \(\delta(q_S,x,u)\rightarrow (q_{B},u)\)​, where \(u\in \Gamma\)​,

  • \(\delta(q_S,z,u)\rightarrow (q_{S},u)\)​, where \(u\in \Gamma\)​,

  • \(\delta(q_S,y,u)\rightarrow (q_{S},u)\)​, where \(u\in \Gamma\)​,

  • \(\delta(q_{B},x,u)\rightarrow (q_{x},uXX)\)​, where \(u\in \Gamma\)​,

  • \(\delta(q_{B},z,u)\rightarrow (q_{S},u)\)​, where \(u\in \Gamma\)​,

  • \(\delta(q_{B},y,u)\rightarrow (q_{S},u)\)​, where \(u\in \Gamma\)​,

  • \(\delta(q_0,x,u)\rightarrow (q_x,u)\)​, where \(u\in \Gamma\)​,

  • \(\delta(q_0,z,u)\rightarrow (q_0,u)\)​, where \(u\in \Gamma\)​,

  • \(\delta(q_0,y,u)\rightarrow (q_0,u)\)​, where \(u\in \Gamma\)​,

  • \(\delta(q_x,x,u)\rightarrow (q_x,uX)\)​, where \(u\in \Gamma\)​,

  • \(\delta(q_x,z,X)\rightarrow (q_0,\epsilon)\)​,

  • \(\delta(q_x,z,\mathop{\mathrm{S}})\rightarrow (q_r,X)\)​, where \(u\in \Gamma\)​,

  • \(\delta(q_x,y,u)\rightarrow (q_0,u)\)​, where \(u\in \Gamma\)​, and

  • \(\delta(q_r,a,u)\rightarrow(q_r,u)\)​, where \(r\in \Sigma_{2k-1}\)​ and \(u\in \Gamma\)​.

Note that the letters from \(\mathop{\mathrm{\Sigma}}_{2k-1}\setminus\{x,y,z\}\)​ change neither the state of \(g_{k,m}\)​ nor the stack. Hence to illuminate the behavior of \(g_{k,m}\)​, we can consider only words over the alphabet \(\{x,y,z\}\)​. Then it is easy to see that the pushdown automaton \(g_{k,m}\)​ pushes \(XX\)​ on the stack on the first occurrence of \(xx\)​. For every other occurrence of \(xx\)​ the pushdown automaton \(g_{k,m}\)​ pushes \(X\)​ on the stack. Once reached the state \(q_x\)​, then for every occurrence of \(xz\)​ one \(X\)​ is removed from the stack. The state \(q_r\)​ works as a refuse state. Note that after reaching the state \(q_r\)​ the stack is not empty, the stack cannot be changed, and no other state can be reached from \(q_r\)​. The states \(q_S\)​ and \(q_B\)​ enable to recognize the first occurrence of \(xx\)​. Once the states \(q_x\)​ are reached, the states \(q_S\)​ and \(q_B\)​ can not be reached any more.

Thus the pushdown automaton \(g_{k,m}\)​ accepts all words, where the number of occurrences of \(xz\)​ after the first occurrence of \(xx\)​ is exactly one more than the number of occurrences of \(xx\)​. Formally, if \(w\in \mu_{k,m}(\mathop{\mathrm{\Sigma}}_{2k-1}^*)\)​ then we define \(\bar w\)​ as follows:

  • If \(\mathop{\mathrm{occur}}(w,xx)=0\)​ then \(\bar w=\epsilon\)​.

  • If \(\mathop{\mathrm{occur}}(w,xx)\geq 1\)​ then let \(\bar w\in \mathop{\mathrm{Suf}}(w)\)​ be such that \(xx\in\mathop{\mathrm{Pref}}(\bar w)\)​ and \(\mathop{\mathrm{occur}}(\bar w,xx)=\mathop{\mathrm{occur}}(w,xx)\)​.

Clearly \(\bar w\)​ is uniquely defined. Then we have that \(w\in \mu_{k,m}(\Lambda_{k,m})\)​ if and only if \(\bar w=\epsilon\)​ or \(\mathop{\mathrm{occur}}(\bar w,xx)+1=\mathop{\mathrm{occur}}(\bar w,xz)\)​. It follows that the words without any occurrence of \(xx\)​ are accepted. In the following we will consider the words from the intersection \(U=\Lambda_{k,m}\cap\mathop{\mathrm{Naw}}_{k,m}\)​. Note that there are only two nonempty words \(xzy,xzzy\in U\)​, that have no occurrence of \(xx\)​.

Recall that a “standard” non-associative word can be represented as a full binary rooted tree graph, where every inner node represents a corresponding pair of brackets and every leaf represents the letter \(z\)​. It is know that the number of inner nodes plus one is equal to the number of leaves in a full binary rooted tree graph. In the case of non-associative words from \(\mathop{\mathrm{Naw}}_{k,m}\)​, let the leaves represent the factors \(xzy\)​ and \(xzzy\)​. Then the number of occurrences of \(xz\)​ is equal to the number of leaves and the number of occurrences of \(xx\)​ is equal to the number of inner nodes. Hence the intersection \(M\cap\mathop{\mathrm{Naw}}_{k,m}\)​ contains non-associative words that have no “unnecessary” brackets; for example \(xzzy, xxzzyy, xxxzzyyy\in \mathop{\mathrm{Naw}}_{k,m}\)​, \(xzzy\in M\)​ and \(xxzzyy, xxxzzyyy\not\in M\)​.

Let \(\mathop{\mathrm{Bal}}_{k,m}\subseteq \mathop{\mathrm{\Sigma}}_{2k-1}^*\)​ be the context free language generated by the following context free grammar, where \(S\)​ is a start non-terminal symbol, \(N,K,V,P\)​ are non-terminal symbols, and \(x,y,z,a\)​ are terminal symbols (the letters from \(\mathop{\mathrm{\Sigma}}_{2k-1}\)​).

  • \(\mathop{\mathrm{S}}\rightarrow KVP\)​,

  • \(V\rightarrow VV\mid \mathop{\mathrm{N}}z\mathop{\mathrm{N}}\mid \mathop{\mathrm{N}}z T z\mathop{\mathrm{N}}\mid \epsilon\)​,

  • \(T\rightarrow \mathop{\mathrm{N}}y\mathop{\mathrm{N}}T\mathop{\mathrm{N}}x\mathop{\mathrm{N}}\mid \epsilon\)​,

  • \(K\rightarrow KK\mid \mathop{\mathrm{N}}x\mathop{\mathrm{N}}\mid \epsilon\)​,

  • \(P\rightarrow PP \mid \mathop{\mathrm{N}}y\mathop{\mathrm{N}}\mid \epsilon\)​,

  • \(\mathop{\mathrm{N}}\rightarrow a\mathop{\mathrm{N}}\mid \epsilon\)​, where \(a\in \mathop{\mathrm{\Sigma}}_{2k-1}\setminus\{x,y,z\}\)​.

We call the words from \(\mathop{\mathrm{Bal}}_{k,m}\)balanced words.

Let \(M=\mu_{k,m}(\mathop{\mathrm{Bal}}_{k,m})\)​. It is easy to see that the words from the language \(M\)​ contains no factor of the form \(zy^ix^jz\)​, where \(i,j\)​ are distinct positive integers; hence the name “balanced” words. The non-terminal symbols \(K,P\)​ enable that if \(w\in M\)​ then \(w\)​ has a prefix \(x^i\)​ and a suffix \(y^j\)​ for some \(i,j\in \mathbb{N}\cup\{0\}\)​.

The non-terminal symbol \(\mathop{\mathrm{N}}\)​ in the definition of \(\mathop{\mathrm{Bal}}_{k,m}\)​ has the same purpose like in the definition of \(\mathop{\mathrm{Naw}}_{k,m}\)​.

Let

\[\begin{equation}\mathop{\mathrm{\Omega}}_{k,m}=\mathop{\mathrm{Naw}}_{k,m}\cap \mathop{\mathrm{Bal}}_{k,m}\cap \Lambda_{k,m}\mbox{.}\end{equation}\]

We call the words from \(\mathop{\mathrm{\Omega}}_{k,m}\)balanced non-associative words over the opening bracket \(x\)​, the closing bracket \(y\)​, and a letter \(z\)​.

Let \(\mathop{\mathrm{\Omega}}_{k,m}(n)=\{w\in \mathop{\mathrm{\Omega}}_{k,m}\mid \mathop{\mathrm{occur}}(w,z)=n\}\)​, where \(n\in \mathbb{N}\)​. The set \(\mathop{\mathrm{\Omega}}_{k,m}(n)\)​ contains the balanced non-associative words having exactly \(n\)​ occurrences of the letter \(z\)​.

Given a word \(w\in \mathop{\mathrm{\Sigma}}_{2k-1}^*\)​ and \(a\in \mathop{\mathrm{\Sigma}}_{2k-1}\)​, let

\[\begin{equation}\mathop{\mathrm{height}}(w,a)=\max\{j\mid a^j\in \mathop{\mathrm{Fac}}(w)\}\mbox{.}\end{equation}\]

The height of a word \(w\)​ is the maximal power of the letter \(a\)​, that is a factor of \(w\)​. We show that if \(w\in \mu_{k,m}(\mathop{\mathrm{\Omega}}_{k,m})\)​ and \(h\)​ is the height the opening bracket \(x\)​ in \(w\)​ then \(x^h\)​ is a prefix of \(w\)​ and \(y^h\)​ is a suffix of \(w\)​.

[oiu33888weu3] If \(w\in \mu_{k,m}(\mathop{\mathrm{\Omega}}_{k,m})\)​ and \(h=\mathop{\mathrm{height}}(w,x)\)​ then \(x^h\in \mathop{\mathrm{Pref}}(w)\)​ and \(y^h\in \mathop{\mathrm{Suf}}(w)\)​.

Note that \(\mu_{k,m}(\mathop{\mathrm{\Omega}}_{k,m})\subseteq\mathop{\mathrm{\Omega}}_{k,m}\)​. Since \(\mathop{\mathrm{\Omega}}_{k,m}\subseteq\mathop{\mathrm{Naw}}_{k,m}\)​, there is \(\bar h\in\mathbb{N}\)​ such that \(x^{\bar h}z\in \mathop{\mathrm{Pref}}(w)\)​. To get a contradiction suppose that \(\bar h<h\)​. Because \(\mathop{\mathrm{\Omega}}_{k,m}\subseteq \mathop{\mathrm{Bal}}_{k,m}\)​ it follows that \(w=x^{\bar h}w_1zy^hx^hzw_2\)​ for some \(w_1\in \mathop{\mathrm{Fac}}(w)\)​ with \(z\in \mathop{\mathrm{Pref}}(w_1z)\)​ and \(w_2\in \mathop{\mathrm{Suf}}(w)\)​.

Consider the prefix \(r=x^{\bar h}w_1zy^h\)​. Obviously \(w_1z\in \mu_{k,m}(\mathop{\mathrm{Bal}}_{k,m})\)​. It is easy to see that if \(v\in \mu_{k,m}(\mathop{\mathrm{Bal}}_{k,m})\)​, \(x\not\in\mathop{\mathrm{Pref}}(v)\)​ and \(y\not\in\mathop{\mathrm{Suf}}(v)\)​ then \(\mathop{\mathrm{occur}}(v,x)=\mathop{\mathrm{occur}}(v,y)\)​. Thus \(\mathop{\mathrm{occur}}(w_1z,x)=\mathop{\mathrm{occur}}(w_1z,y)\)​. It follows that \(\mathop{\mathrm{occur}}(r,x)<\mathop{\mathrm{occur}}(r,y)\)​.

This is a contradiction, since for every prefix \(v\in \mathop{\mathrm{Pref}}(w)\)​ of a non-associative word \(w\in \mathop{\mathrm{Naw}}_{k,m}\)​ we have that \(\mathop{\mathrm{occur}}(v,x)\geq\mathop{\mathrm{occur}}(v,y)\)​. We conclude that \(\bar h=h\)​ and \(x^h\in \mathop{\mathrm{Pref}}(w)\)​. In an analog way we can show that \(y^h\in \mathop{\mathrm{Suf}}(w)\)​. This completes the proof.

For a word \(w\in \mu_{k,m}(\mathop{\mathrm{\Omega}}_{k,m})\)​, we show the relation between the height of \(w\)​ and the number of occurrences of \(z\)​ in \(w\)​.

[ryybvnmd73yrh] If \(w\in \mu_{k,m}(\mathop{\mathrm{\Omega}}_{k,m})\)​ and \(h=\mathop{\mathrm{height}}(w,x)\)​ then

\[\begin{equation}2^{h-1}\leq\mathop{\mathrm{occur}}(w,z)\leq 2^h\mbox{.}\end{equation}\]

We prove the proposition for all \(h\)​ by induction:

  • If \(h=0\)​ then \(w=\epsilon\)​.

  • If \(h=1\)​ then \(w\in \{xzzy, xzy\}\)​.

  • If \(h=2\)​ then \(w\in\{xxzyxzyy, xxzzyxzyy, xxzyxzzyy, xxzzyxzzyy\}\mbox{.}\)

Thus the proposition holds for \(h\leq 2\)​ and clearly we have that if \(h\geq 2\)​ then \(w=xw_1w_2y\)​, where \(w_1, w_2\in \mu_{k,m}(\mathop{\mathrm{\Omega}}_{k,m})\)​. Suppose the proposition holds for all \(\bar h<h\)​. We prove the proposition holds for \(h\)​.

Let \(h_1=\mathop{\mathrm{height}}(w_1,x)\)​ and \(h_2=\mathop{\mathrm{height}}(w_2,x)\)​. Lemma ??? implies that \(x^{h_1}\in \mathop{\mathrm{Pref}}(w_1)\)​, \(y^{h_1}\in\mathop{\mathrm{Suf}}(w_1)\)​, \(x^{h_2}\in \mathop{\mathrm{Pref}}(w_2)\)​, and \(y^{h_2}\in\mathop{\mathrm{Suf}}(w_2)\)​. Since \(w\in \mu_{k,m}(\mathop{\mathrm{Bal}}_{k,m})\)​ it follows that \(h_1=h_2\)​. Because \(x^{h_1}\in \mathop{\mathrm{Pref}}(w_1)\)​ we have that \(x^{h_1+1}\in \mathop{\mathrm{Pref}}(w)\)​. Clearly \(\mathop{\mathrm{occur}}(w,x^{h_1+1})=1\)​; note that \(\mathop{\mathrm{occur}}(w_1w_2, x^{h_1+1})=0\)​. Thus \(h_1+1=h\)​. For we assumed that the proposition holds for all \(\bar h<h\)​, we can derive that

\[\begin{equation}\mathop{\mathrm{occur}}(w,z)=\mathop{\mathrm{occur}}(w_1,z)+\mathop{\mathrm{occur}}(w_2,z)\leq 2^{h_1}+2^{h_1}=2^{h_1+1}=2^h\end{equation}\]

and

\[\begin{equation}\mathop{\mathrm{occur}}(w,z)=\mathop{\mathrm{occur}}(w_1,z)+\mathop{\mathrm{occur}}(w_2,z)\geq 2^{h_1-1}+2^{h_1-1}=2^{h_1}=2^{h-1}\mbox{.}\end{equation}\]

This completes the proof.

Proposition ??? have the following obvious corollary.

[rryt7fufyu3y] If \(n\in\mathbb{N}\)​, \(w\in \mu_{k,m}(\mathop{\mathrm{\Omega}}_{k,m}(n))\)​, and \(h=\mathop{\mathrm{height}}(w,x)\)​ then

\[\begin{equation}\log_2{n}\leq h\leq1+\log_2{n}\mbox{.}\end{equation}\]

Given \(w,u,v\in \mathop{\mathrm{\Sigma}}_{2k-1}^+\)​, let \(\mathop{\mathrm{replace}}(w,v,u)\)​ denote the word built from \(w\)​ by replacing the first occurrence of \(v\)​ in \(w\)​ by \(u\)​. Formally, if \(\mathop{\mathrm{occur}}(w,v)=0\)​ then \(\mathop{\mathrm{replace}}(w,v,u)=w\)​. If \(\mathop{\mathrm{occur}}(w,v)=j>0\)​ and \(w=w_1vw_2\)​, where \(\mathop{\mathrm{occur}}(vw_2,v)=j\)​ then \(\mathop{\mathrm{replace}}(w,v,u)=w_1uw_2\)​.

We prove that the set of balanced non-associative words \(\mathop{\mathrm{\Omega}}_{k,m}(n)\)​ having \(n\)​ occurrences of \(z\)​ is nonempty for each \(n\in\mathbb{N}\)​.

[un7bbv3b] If \(n\in \mathbb{N}\)​ then \(\mathop{\mathrm{\Omega}}_{k,m}(n)\not=\emptyset\)​.

If \(n=1\)​ then \(xzy\in \mathop{\mathrm{\Omega}}_{k,m}(1)\)​. Given \(n\in \mathbb{N}\)​ with \(n>1\)​, let \(j\in\mathbb{N}\)​ be such that \(2^{j-1}<n\leq 2^j\)​. Obviously such \(j\)​ exists and is uniquely determined. Let \(w_1=xzzy\)​. Let \(w_{i+1}=xw_iw_iy\)​. Clearly \(\mathop{\mathrm{occur}}(w_j,z)=2^j\)​ and \(w_j\in\mathop{\mathrm{\Omega}}_{k,m}(2^j)\)​. Note that \(\mathop{\mathrm{occur}}(w_j,xzzy)=2^{j-1}\)​. Let \(w_{j,0}=w_j\)​ and \(w_{j,i+1}=\mathop{\mathrm{replace}}(w_{j,i},xzzy,xzy)\)​. Let \(\alpha=2^j-n\)​. Then one can easily verify that \(\mathop{\mathrm{occur}}(w_{j,\alpha},z)=n\)​ and \(w_{j,\alpha}\in\mathop{\mathrm{\Omega}}_{k,m}(n)\)​.

Less formally said, we construct a balanced non-associative word \(w_j\)​ having \(2^{j-1}\)​ occurrences of \(xzzy\)​ and then we replace a given number of occurrences of \(xzzy\)​ with the factor \(xzy\)​ to achieve the required number of occurrences of \(z\)​. This completes the proof. \(\qed\)

4 Intersection of balanced non-associative words

Let \(\mathop{\mathrm{\Omega}}_k=\bigcap_{m=2}^k\mathop{\mathrm{\Omega}}_{k,m}\)​ and let \(\mathop{\mathrm{\Omega}}_k(n)=\{w\in \mathop{\mathrm{\Omega}}_k\mid \mathop{\mathrm{occur}}(w,x_1)=n\}\)​. We show that for all positive integers \(n,k\)​ with \(k\geq 2\)​ there is a word \(w\in\mathop{\mathrm{\Omega}}_k\)​ such that \(w\)​ has \(n\)​ occurrences of the opening bracket \(x_1\)​.

[ry7g84j9d09] If \(k,n\in\mathbb{N}\)​ and \(k\geq 2\)​ then \(\mathop{\mathrm{\Omega}}_{k}(n)\not=\emptyset\)​.

Let \(h(1)=n\)​. Let \(w_i\in \mu_{k,i}(\mathop{\mathrm{\Omega}}_{k,i}(h(i-1))\)​ and let \(h(i)=\mathop{\mathrm{height}}(w_i,x_i)\)​, where \(i\in\{2,3,4,\dots,k\}\)​. Lemma ??? implies that such \(w_i\)​ exist.

Let \(v_2=w_2\)​. Let \(v_{j+1}=\mathop{\mathrm{replace}}(v_j,x_j^{h(j)},w_{j+1})\)​. Note that \(\mu_{k,j}(v_j+1)=\mu_{k,j}(v_j)\)​. Then it is quite straightforward to see that \(v_k\in \mathop{\mathrm{\Omega}}_k\)​ and \(\mathop{\mathrm{occur}}(v_k,x_1)=n\)​. This completes the proof. \(\qed\)

To clarify the proof of Proposition ???, let us see the following example.

Let \(n=23\)​ and \(k=4\)​. To make the example easy to read, we define \(\mathop{\mathrm{B}}_4=\{z,(,[,<\}\)​ and \(\bar \mathop{\mathrm{B}}_4=\{\bar z,),],>\}\)​. It means that \(x_1=z\)​, \(x_2=(\)​, \(x_3=[\)​, \(x_4=<\)​, \(\bar x_1=\bar z\)​, \(\bar x_2=)\)​, \(\bar x_3=]\)​, and \(\bar x_4=>\)​.

To fit the example into the width of the page, we define auxiliary words \(u_1\)​ and \(u_2\)​:

  • \(u_1=z)(z))((z)(z)))(((z)(z))((z)(z))))\)​,

  • \(u_2=((((z)(zz))((zz)(zz)))(((zz)(zz))((zz)(zz)))))\)​.

Then we have that

  • \(h(1)=23\)​; \(w_2=(((((u_1u_2\)​; \(h(2)=5\)​; \(w_3=[[[(][(]][[(][((]]]\)​;

  • \(h(3)=3\)​; \(w_4=<<[[><[[>>\)​; \(h(4)=2\)​; \(v_2=w_2\)​;

  • \(v_3=[[[(][(]][[(][((]]]u_1u_2\)​;

  • \(v_4=<<[><[[>>(][(]][[(][((]]]]u_1u_2\)​.

This ends the example.

We define two technical functions \(\log_2^{(j)}{t}\)​ and \(\log_2^{[j]}{t}\)​ for all \(j\in \mathbb{N}\)​ and \(t\in \mathbb{R}^+\)​ as follows:

  • \(\log_2^{(1)}{t}=\log_2{t}\)​ and \(\log_2^{(j+1)}{t}=\log_2^{(j)}{(\log_2{t})}\)​.

  • \(\log_2^{[1]}{t}=1+\log_2{t}\)​ and \(\log_2^{[j+1]}{t}=\log_2^{[j]}{(1+\log_2{t})}\)​.

It is a simple exercise to prove the following lemma. We omit the proof.

[tt7tytu7n] If \(j\in \mathbb{N}\)​ then there is a constants \(c_1\in \mathbb{R}^+\)​ such that for each \(t\in \mathbb{R}^+\)​ with \(t\geq 1\)​ we have

\[\begin{equation}\log_2^{(j)}{t}\leq \log_2^{[j]}{t} \leq c_1+\log_2^{[j]}{t}\mbox{.}\end{equation}\]

Note in Lemma ??? that the constant \(c_1\)​ depends on \(j\)​.

Using the function \(\log_2^{(k)}{t}\)​ we present an upper and a lower bound for the height of words from \(\mathop{\mathrm{\Omega}}_k\)​.

[ty7cbn2bbg] If \(k\in \mathbb{N}\)​, \(k\geq 2\)​ then there is a constants \(c_1\in \mathbb{R}^+\)​ such for each \(w\in \mathop{\mathrm{\Omega}}_k\)​, \(h=\mathop{\mathrm{height}}(w,x_k)\)​, and \(n=\mathop{\mathrm{occur}}(w,x_1)\)​ we have

\[\begin{equation}\log_2^{(k)}{n}\leq h\leq c_1+\log_2^{(k)}{n}\mbox{.}\end{equation}\]

It follows from Corollary ??? that \(\log_2^{(k)}{n}\leq h\leq\log_2^{[k]}{n}\mbox{.}\)​ Then the proposition follows from Lemma ???. \(\qed\)

Note in Proposition ??? that the constant \(c_1\)​ depends on \(k\)​.

5 Dissection by a regular language

In [6] it was shown that every constantly growing language can be dissected by some regular language.

(see [6]) Every infinite constantly growing language is \(REG\)​-dissectible.

From the proof of Lemma \(3.3\)​ in [6] we can formulate the following Lemma.

[turk3j998tj] If \(n,c_0\in\mathbb{N}\)​, \(K\subset\mathbb{N}\)​, \(\vert K\vert <\infty\)​, \(c=\max\{j\in K\}\)​, and \(L\subseteq\mathop{\mathrm{\Delta}}_n^*\)​ is a \((c_0,K)\)​-constantly growing language then there are \(j_1,j_2\in\{0,1,2,\dots,c\}\)​ such that both sets \(H_1,H_2\)​ are infinite, where

\[\begin{equation}H_i=\{w\mid w\in L\mbox{ and }\vert w\vert\equiv j_i\pmod{c+1}\}\mbox{ and }i\in\{1,2\}\mbox{.}\end{equation}\]

6 Tetration

Recall that a deterministic finite automaton \(g\)​ is \(5\)​-tuple \((\mathop{\mathrm{Q}},\mathop{\mathrm{\Delta}}, q_0,\delta,\mathop{\mathrm{F}})\)​, where \(\mathop{\mathrm{Q}}\)​ is the set of states, \(\mathop{\mathrm{\Delta}}\)​ is an input alphabet, \(q_0\)​ is the initial state, \(\delta\)​ is a transition function, and \(\mathop{\mathrm{F}}\)​ is the set of accepting states. Let \(\mathop{\mathrm{AL}}(g)\)​ denote the language accepted by \(g\)​; \(\mathop{\mathrm{AL}}(g)\)​ is a regular language.

We prove that if \(L\subseteq\mathop{\mathrm{\Omega}}_k\)​ is an infinite language of balanced non-associative words with the number of occurrences of \(x_1\)​ “bounded” by \((k,\alpha)\)​-tetration then \(L\)​ can be dissected by a regular language.

[rujfkie778d] If \(k,\alpha\in \mathbb{N}\)​, \(k\geq 2\)​, and \(L\subseteq \mathop{\mathrm{\Omega}}_k\)​ is an infinite language such that for each \(w_1\in L\)​ there is \(w_2\in L\)​ with \(\mathop{\mathrm{occur}}(w_2,x_1)\leq \exp^{k,\alpha}\mathop{\mathrm{occur}}(w_1,x_1)\)​ then there is a regular language \(R\)​ such that \(R\)​ dissects \(L\)​.

Let \(w_1,w_2\in L\)​ be such that

\[\begin{equation}n_2\leq \exp^k_{\alpha}n_1\mbox{,}\label{ryd7wuy37y}\end{equation}\] where \(n_1=\mathop{\mathrm{occur}}(w_1,x_1)\)​ and \(n_2=\mathop{\mathrm{occur}}(w_2,x_1)\)​.

Let \(h_1=\mathop{\mathrm{height}}(\mu_{k,k}(w_1),x_k)\)​ and \(h_2=\mathop{\mathrm{height}}(\mu_{k,k}(w_2),x_k)\)​. Proposition ??? implies that there is a constants \(c_1\in \mathbb{R}^+\)​ such that

\[\begin{equation}h_1\geq \log_2^{(k)}n_1 \mbox{ and }h_2\leq c_1+\log_2^{(k)}n_2\label{ty7uyr7uq33}\end{equation}\]

Note that the constant \(c_1\)​ does not depend on \(n_1,n_2,h_1,h_2\)​. On the other hand the constant depends on \(k\)​.

From (\(\ref{ryd7wuy37y}\)) and (\(\ref{ty7uyr7uq33}\)) we have that \[\begin{equation}h_2\leq c_1+\log_2^{(k)}n_2\leq c_1+ \log_2^{(k)}(\exp^{k,\alpha}n_1)\mbox{.}\label{rr6fhbsve} \end{equation}\]

Realize that \(\log_2(\exp^{j,\alpha})=\exp^{j-1,\alpha}\)​ and that if \(a,b\in\mathbb{R}^+\)​ and \(a,b\geq 2\)​ then \(a+b\leq ab\)​. Then we have that

\[\begin{equation}\log_2^{(j)}(\exp^{j,\alpha}n_1)=\log_2^{(j-1)}(\exp^{j-1,\alpha}+\log_2{n_1})\leq \log_2^{(j-1)}(\exp^{j-1,\alpha}\log_2{n_1})\mbox{.}\label{dyeuejruy33}\end{equation}\]

From (\(\ref{dyeuejruy33}\)) it follows that

\[\begin{equation}\log_2^{(k)}(\exp^{k,\alpha}n_1)\leq \log_2(\exp^{1,\alpha}\log_2^{(k-1)}{n_1})=\alpha+\log_2^{(k)}{n_1}\mbox{.}\label{gdt552vc}\end{equation}\]

From (\(\ref{ty7uyr7uq33}\)), (\(\ref{rr6fhbsve}\)), and (\(\ref{gdt552vc}\)) we have that

\[\begin{equation}h_2\leq c_1+\alpha+\log_2^{(k)}{n_1}\leq c_1+\alpha+h_1\mbox{.}\label{rbnch76tgrg}\end{equation}\]

The equation (\(\ref{rbnch76tgrg}\)) says that there is a constant \(c\in \mathbb{N}\)​ such that for each \(u\in L\)​ there is \(v\in L\)​ with \(h_2\leq c+h_1\)​.

Lemma ??? implies that there are \(j_1,j_2\)​ such that both \(H_1,H_2\)​ are infinite sets, where

\[\begin{equation}H_i=\{v\mid v\in L\mbox{ and }\mathop{\mathrm{height}}(\mu_{k,k}(v),x_k)\equiv j_i\pmod{c+1}\}\mbox{ and }i\in\{1,2\}\mbox{.}\end{equation}\]

Consider the deterministic finite automaton \(g=(\mathop{\mathrm{Q}},\mathop{\mathrm{\Sigma}}_{2k-1}, q_0,\delta,\mathop{\mathrm{F}})\)​, where

  • \(\mathop{\mathrm{Q}}=\{q_0,q_1,\dots,q_{c}, q_a,q_r\}\)​,

  • \(\delta(q, x)\rightarrow (q)\)​, where \(q\in\mathop{\mathrm{Q}}\)​ and \(x\in\mathop{\mathrm{\Sigma}}_{2k-1}\setminus\{x_k,x_{k-1}\}\)​,

  • \(\delta(q_i,x_k)\rightarrow(q_{i+1\mod{c+1}})\)​,

  • \(\delta(q_{j_1}, x_{k-1})\rightarrow (q_a)\)​,

  • \(\delta(q_i, x_{k-1})\rightarrow (q_r)\)​, where \(i\not=j_1\)​,

  • \(\delta(q, x)\rightarrow (q)\)​, where \(q\in\{q_a,q_r\}\)​ and \(x\in \mathop{\mathrm{\Sigma}}_{2k-1}\)​, and

  • \(\mathop{\mathrm{F}}=\{q_{j_1},q_a\}\)​.

The deterministic finite automaton \(g\)​ implements the modulo operation on the prefix of the form \(x_k^i\)​. The input letter \(x\in\mathop{\mathrm{\Sigma}}_{2k-1}\setminus\{x_k,x_{k-1}\}\)​ does not change the state. The input letter \(x_k\)​ changes the state from \(q_i\)​ to \(q_{i+1\mod{c+1}}\)​. If the input letter equals \(x_{k-1}\)​ then the state changes either to accept \(q_a\)​ or refuse \(q_r\)​. Realize that if \(w\in \mu_{k,k}(\mathop{\mathrm{\Omega}}_k)\)​, \(a\in \{x_k,y_k,x_{k-1}\}\)​, and \(x_ka\in\mathop{\mathrm{Fac}}(w)\)​ then \(a\in \{x_k,x_{k-1}\}\)​. Once in the state \(q_a\)​ or \(q_r\)​, no other states can be reached. The states \(q_{j_1}\)​ and \(q_a\)​ are the accepting states. It is easy to see that \(\mathop{\mathrm{AL}}(g)=H_1\)​ and in consequence the regular language \(R=\mathop{\mathrm{AL}}(g)\)​ dissects \(L\)​.

This completes the proof. \(\qed\)

Given \(n\in \mathbb{N}\)​, let \(\mathop{\mathrm{\Delta}}_n\)​ be some alphabet with \(n\)​ letters. Let \(\mathop{\mathrm{\Delta}}_1=\mathop{\mathrm{B}}_1=\{x_1\}\)​ be the alphabet with the “first” opening bracket. Let \(L\subseteq\mathop{\mathrm{\Delta}}_n^*\)​ be an infinite language with a growing bounded by \((k,\alpha)\)​-tetration. Let \(\upsilon: \mathop{\mathrm{\Sigma}}_{2k-1}^*\rightarrow \mathop{\mathrm{\Delta}}_1\)​ be an erasing alphabetical homomorphism defined by \(\upsilon(x_1)=x_1\)​ and \(\upsilon(a)=\epsilon\)​, where \(a\in \mathop{\mathrm{\Sigma}}_{2k-1}\setminus\{x_1\}\)​. Let \(\pi: \mathop{\mathrm{\Delta}}_n^*\rightarrow \mathop{\mathrm{\Delta}}_1\)​ be an alphabetical homomorphism defined by \(\upsilon(a)=x_1\)​ for all \(a\in \mathop{\mathrm{\Delta}}_n\)​. Note that if \(w\in\mathop{\mathrm{\Delta}}_n^*\)​ then \(\vert w\vert=\vert \pi(w)\vert\)​.

We show that there \(3k-3\)​ context free languages \(L_1,L_2,\dots,L_{3k-3}\subseteq \mathop{\mathrm{\Sigma}}_{2k-1}^*\)​ such that the homomorphic image \(\upsilon(\bigcap_{i}^{3k}L_i)\)​ dissects the homomorphic image \(\pi(L)\)​.

If \(n, \alpha, k\in\mathbb{N}\)​, \(k\geq 2\)​, \(L\subseteq\mathop{\mathrm{\Delta}}_n^*\)​ is an infinite language with the growth bounded by \((k,\alpha)\)​-tetration then there are \(3k-3\)​ context free languages \(L_1,L_2,\dots,L_{3k-3}\)​ such that \(\upsilon(\bigcap_{i}^{3k-3}L_i)\)​ dissects \(\pi(L)\)​.

Recall that the language \(\mathop{\mathrm{\Omega}}_k\)​ is an intersection of \(3k-3\)​ context free languages:

\[\begin{equation}\mathop{\mathrm{\Omega}}_k=\bigcap_{m=2}^k\left(\mathop{\mathrm{Naw}}_{k,m}\cap\mathop{\mathrm{Bal}}_{k,m}\cap\Lambda_{k,m}\right)\mbox{.}\end{equation}\]

Let us denote these languages \(L_1,L_2,\dots,L_{3k-3}\)​. Let \(\pi(L)=\{\pi(w)\mid w\in L \}\subseteq \mathop{\mathrm{\Delta}}_1^*\)​ and let \(\bar L=\{w\in \mathop{\mathrm{\Omega}}_k\mid \upsilon(w)\in \pi(L)\}\mbox{.}\)​ Note that \(\bar L\)​ contains \(w\in \Omega_k\)​ if and only if there is \(\bar w\in L\)​ such that the number of occurrences of \(x_1\)​ in \(w\)​ is equal to the length of \(\bar w\)​; formally \(\mathop{\mathrm{occur}}(w,x_1)=\vert \bar w\vert\)​.

Since \(L\)​ is a language with the growth bounded by \((k,\alpha)\)​-tetration, we have that for each \(w_1\in \bar L\)​ there is \(w_2\in \bar L\)​ with

\[\begin{equation}\mathop{\mathrm{occur}}(w_2,x_1)\leq \exp^{k,\alpha}\mathop{\mathrm{occur}}(w_1,x_1)\mbox{.}\end{equation}\]

Then Proposition ??? implies that there is a regular language \(R\)​ that dissects \(\bar L\)​. It is well known that intersection of a regular language and a context free language is a context free language. Hence let \(\bar L_1=L_1\cap R\)​. Then \(\bar L_1\cap\left(\bigcap_{i=2}^{3k-3}L_i\right)\)​ dissects \(\bar L\)​. The theorem follows. \(\qed\)

Acknowledgments

This work was supported by the Grant Agency of the Czech Technical University in Prague, grant No. SGS20/183/OHK4/3T/14.

References

[1] Ginsburg, S., Greibach, S.: Deterministic context free languages. Information and Control 9(6), 620 – 648 (1966). https://doi.org/10.1016/S0019-9958(66)80019-0.

[2] Liu, L., Weiner, P.: An infinite hierarchy of intersections of context-free languages. Math. Systems Theory 7, 185–192. (1973,).

[3] Wotschke, D.: The Boolean Closures of the Deterministic and Nondeterministic Context-Free Languages, pp. 113–121. Springer Berlin Heidelberg, Berlin, Heidelberg (1973). https://doi.org/10.1007/978-3-662-41148-3_11.

[4] Wotschke, D.: Nondeterminism and boolean operations in pda’s. Journal of Computer and System Sciences 16(3), 456 – 461 (1978). https://doi.org/10.1016/0022-0000(78)90030-2.

[5] Yamakami, T.: Intersection and union hierarchies of deterministic context-free languages and pumping lemmas. In: Leporati, A., Martín-Vide, C., Shapira, D., Zandron, C. (eds.) Language and Automata Theory and Applications. pp. 341–353. Springer International Publishing, Cham (2020).

[6] Yamakami, T., Kato, Y.: The dissecting power of regular languages. Information Processing Letters 113(4), 116 – 122 (2013). https://doi.org/10.1016/j.ipl.2012.12.006.

[7] Bucher, W.: A density problem for context-free languages. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 10 (1980).

[8] Julie, J., Baskar Babujee, J., Masilamani, V.: Dissecting power of certain matrix languages. In: Arumugam, S., Bagga, J., Beineke, L.W., Panda, B. (eds.) Theoretical Computer Science and Discrete Mathematics. pp. 98–105. Springer International Publishing, Cham (2017).

[9] Domaratzki, M., Shallit, J., Yu, S.: Minimal covers of formal languages. In: Developments in Language Theory (2001).

[10] Flajolet, P., Steyaert, J.M.: On sets having only hard subsets. In: Loeckx, J. (ed.) Automata, Languages and Programming. pp. 446–457. Springer Berlin Heidelberg, Berlin, Heidelberg (1974).

[11] Post, E.L.: Recursively enumerable sets of positive integers and their decision problems. Bull. Amer. Math. Soc. 50(5), 284–316 (05 1944), https://projecteuclid.org:443/euclid.bams/1183505800.


  1. Department of Mathematics, Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University in Prague (josef.rukavicka@seznam.cz).↩︎