Tree-controlled grammars with restrictions placed upon cuts and paths (Q2893941)

Tree controlled grammars were introduced in [\textit{K. Čulik II.} and \textit{H. A. Maurer}, Computing 19, 129--139 (1977; Zbl 0363.68108)] as a pair \((G,R)\), where \(G\) is a context-free grammar and \(R\) is a regular control language containing words composed of the terminal and nonterminal alphabets of \(G\), and it is used to control the work of \(G\) by restricting the set of derivations which \(G\) is allowed to make. Only those words belong to the generated language which can be generated by the context-free grammar \(G\) having a derivation tree where, for all the strings obtained by reading from left to right, the symbols labeling the nodes which belong to the same level of the tree (with the exception of the last level) are elements of the regular set \(R\).NEWLINENEWLINEThis paper studies variants of this notion, where instead of the words composed of symbols on the same levels of the derivation tree, words obtained by reading along different paths and tree cuts of the derivation trees of \(G\) are required to be in the regular control language \(R\).NEWLINENEWLINERestricting the paths which are allowed in derivation trees of context-free grammars was already considered in [\textit{S. Marcus} et al., in: Computational linguistics in the Netherlands 2000. Selected papers from the 11th workshop (CLIN), Tilburg, Netherlands, November 3, 2000. Amsterdam: Editions Rodopi B. 111--125 (2001; Zbl 0996.68078)], where it was shown that if it is required that the allowed derivation trees contain at least one path belonging to \(R\), then the controlled grammar still generates only context-free languages. In the present paper the authors first show that this holds even if not just one but all paths of the derivation trees must be in \(R\), thus, path controlled grammars generate context-free languages in both cases.NEWLINENEWLINEThen the authors consider the words which can be read along different sets of paths of the derivation trees. First they show that all recursively enumerable languages can be generated if only those derivation trees are allowed which can be covered by a set of cuts in such a way that all the words of the cuts belong to the control language \(R\). Then it is also shown that the generative power of the cut controlled grammars does not change if only those cut sets are considered which do not contain cuts that cross each other (ordered cut controlled grammars).