Is there a class of languages $L(G)$ admitted by a class of phrase structure grammars $G$ equivalent to $\mathbf{PR}$? (the class of primitive recursive languages = $\mathbf{LOOP}$)?

In greater detail: given the well known definition of a grammar $G = (N,\Sigma,P,S)$ with $N$ being a finite set of nonterminal symbols, $\Sigma$ being a finite set of terminal symbols with $N \cap \Sigma = \emptyset$, $S \in N$ being the start symbol and $P$ being a finite set of production rules $P = \{(l_0,l_1,…,l_i)\times(r_0,r_1,…,r_j)^{*}\} \subset \alpha N \beta \rightarrow \gamma$ with $(l_i)\times(r_j) \in (\Sigma \cup N)\times(\Sigma \cup N)$ and $\alpha, \beta, \gamma \in (\Sigma \cup N)^{*}$, does there exist a set of further conditions on $\alpha$, $\beta$ and $\gamma$ only dependend on any of the $l_i$ and $r_j$(in other words, it is a purely syntactic restriction) such that $L(G) = \mathbf{PR}$?

Clearly, since $\mathbf{CSL} \subsetneq \mathbf{PR} \subsetneq \mathbf{RE}$ and both $\mathbf{CSL}$ and $\mathbf{RE}$ admit a grammar formalism (namely the noncontracting or monotonic grammars and the unrestricted grammars), I wondered whether such a formalism might exist for $\mathbf {PR}$ as well.

Contrary to the classes of $\mathbf{CSL}$ and $\mathbf{RE}$, the only known definitions of $\mathbf{PR}$ seem to either use nested functional equations or abstract programming language constructs instead of formal grammars. Extensive search in the academic literature, forums and online didn't gave any answers. It seems this question is an open problem bare of any interest.

I know that many arithmetic functions over the natural numbers can be defined using $\mathbf{PR}$ nested functional equations and that such arithmetic functions can also be defined using string rewriting or formal grammars. However, given the potential complexity by applications of either definitions of $\mathbf{PR}$ and the additional complexity arising by trying to delimit them from $\mathbf{RE}$, it seems unclear to find a phrase structure grammar formalism which generates exactly $\mathbf{PR}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.