Abstract grammars based on transductions (Q1176481): Difference between revisions

A transduction is a mapping \(\sigma: V^*\to 2^{V^*}\) extended to languages over \(V\) by \(\sigma(L)=\cup\{\sigma(x)\mid\;x\in L\}\). For a family \({\mathcal T}\) of transductions, a \({\mathcal T}\)-grammar is a system \(G=(V,\Sigma,U,S)\), where \(V\) is an alphabet, \(\Sigma\subseteq V\), \(S\in V-\Sigma\), and \(U\subseteq {\mathcal T}\). The language generated by \(G\) is \(L(G)=(\cup\{\sigma_ p(\dots(\sigma_ 1(S))\dots)\mid\;p\geq 0,\;\sigma_ i\in U,\;1\leq i\leq p\})\cap\Sigma^*\). If we consider only sequences of transductions \(\sigma_ p\dots\sigma_ 1\) in a given control set \(C\) (in a family \(\Gamma\) of languages), then we speak about \(\Gamma\)-controlled \({\mathcal T}\)-grammars. The generative capacity of such mechanisms (which generalize and are related to many other generative mechanisms in the literature, mainly in \(L\)-systems area) is investigated, as well as decidability and complexity questions. For instance, it is proved that regular control does not increase the generative capacity of \({\mathcal T}\)-grammars, that the number of transductions in such a grammar can be reduced to one or to two, depending on the properties of \({\mathcal T}\), that the emptiness is decidable for \(\Gamma\)-controlled \({\mathcal T}\)-grammars provided the emptiness is decidable for \(\Gamma\) and \({\mathcal T}\), and \(\Gamma\) and \({\mathcal T}\) are closed under intersection by regular sets, etc.