Learning very simple k-Equal Matrix Grammar from positive data

摘要

Siromoney[1] introduced a notion of an Equal matrix grammar which is a kind of a parallel re-writing system and which includes the class of regular languages. Yokomori [4] introduced very simple grammars and studied the problem of identifying this class in the limit from positive data. In this paper, we combine them and introduced a new grammar called Very Simple k-Equal Matrix Grammar. We also study certain properties of the grammar, compare this class with other known classes of languages and show that this class is polynomial time identifiable in the limit from positive data.