Properties of Elementary Formal Systems as Translation Grammars
Noriko Sugimoto, 典子 杉本 · QIR (Kyushu University Institutional Repository) (Kyushu University) · 1995
We show some properties of elementary formal systems (EFS's, for short) as translation grammars. A translation is a binary relation over strings. Since the EFS's are logic programs over strings, they can easily define translations. In this paper, we consider the problem for deciding whether the number of target sentences, which correspond to output strings, is finite or not for any source sentence, which corresponds to an input string. When we need all target sentences, the finiteness of the given translation is important. However, the finiteness problem is unsolvable in general. Therefore, we give a class of translations in which the problem is solvable. On the other hand, for some integer k, a k-bounded translation is defined as the translation in which the number of target sentences is less than or equal to k for any source sentence. Furthermore, we give a class of EFS's which define 1-bounded translations.