Homomorphic characterizations of recursively enumerable languages with very small language classes (Q1589418)

In this paper, we attempt to characterize the class of recursively enumerable languages with much smaller language classes than that of linear languages. Language classes, \((i,j)\) LL and \((i,j)ML,\) of \((i,j)\) linear languages and \((i,j)\) minimal linear languages are defined by posing restrictions on the form of production rules and the number of nonterminals. Then the homomorphic characterizations of the class of recursively enumerable languages are obtained using these classes and a class, \(ML,\) of minimal linear languages. That is, for any recursively enumerable language \(L\) over \(\Sigma\), an alphabet \(\Delta\), a homomorphism \(h: \Delta^{*}\rightarrow \Sigma^{*}\) and two languages \(L_{1}\) and \(L_{2}\) over \(\Delta\) in some classes mentioned above can be found such that \(L = h(L_{1}\cap L_{2})\). The membership relations of \(L_{1}\) and \(L_{2}\) of the main results are as follows: (I) For posing restrictions on the forms of production rules, the following result is obtained: (1) \(L_{1} \in (1,2)\) LL and \(L_{2} \in (1,1)\) LL. This result is the best one and cannot be improved using \((i,j)\) LL. However, with posing more restriction on \(L_{2},\) this result can be improved and the follwing statement is obtained. (2) \(L_{1} \in (1,2)\) LL and \(L_{2} \in (1,1)\) ML. (II) For posing restrictions on the numbers of nonterminals, the follwing result is obtained. (3) \(L_{1} \in \text{ML}\) and \(L_{2} \in (1,1)\) ML. We believe this result is also the best.