Homomorphic characterizations of recursively enumerable languages with very small language classes
type: Item
instance of: scholarly article
title: Homomorphic characterizations of recursively enumerable languages with very small language classes
zbMATH Open document ID: 0952.68075
DOI: 10.1016/S0304-3975(99)00110-3
published in: Theoretical Computer Science
publication date: 2000-12-12T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1542257
zbMATH Keywords: formal language theory
zbMATH Keywords: homomorphic characterization
author: Satoshi Okawa
author: S. Hirose
MaRDI profile type: Publication
Wikidata QID: Q123314526
cites work: On a family of linear grammars
cites work: Generalizations of regular events
cites work: Reversal-bounded multipushdown machines
cites work: One-way stack automata
cites work: A homomorphic characterization of recursively enumerable languages
cites work: Q3948608
cites work: The decidability of equivalence for a family of linear grammars
description: scientific article; zbMATH DE number 1542257