Homomorphic characterizations of recursively enumerable languages with very small language classes
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.
- A homomorphic characterization of recursively enumerable languages
- Generalizations of regular events
- scientific article; zbMATH DE number 3767067 (Why is no real title available?)
- On a family of linear grammars
- One-way stack automata
- Reversal-bounded multipushdown machines
- The decidability of equivalence for a family of linear grammars
- A homomorphic characterization of recursively enumerable languages
- A representation of recursively enumerable languages by two homomorphisms and a quotient
- Separating the classes of recursively enumerable languages based on machine size
- scientific article; zbMATH DE number 58294 (Why is no real title available?)
- scientific article; zbMATH DE number 58295 (Why is no real title available?)
- scientific article; zbMATH DE number 1346364 (Why is no real title available?)
- scientific article; zbMATH DE number 1008508 (Why is no real title available?)
- scientific article; zbMATH DE number 1057351 (Why is no real title available?)
- scientific article; zbMATH DE number 1774219 (Why is no real title available?)
This page was built for publication: Homomorphic characterizations of recursively enumerable languages with very small language classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1589418)
