Polynomial Time Learnability of Deterministic Right Linear Translations

This paper is concerned with the problem of learning translations from minimally adequate teacher. A translation considered here is a binary relation over strings and defined by an elementary formal system (EFS, for short) in a special form. An EFS consists of several predicates, in general, but the defined translation is directly characterized by only one designated predicate in them. This means that every other predicates, which are indirectly necessary for defining the translation, are never ohserved in the interaction between a teacher and a learner. The main problem investigated in this paper is how to inventing such unobserved predicates and to complete learning. The presented algorithm learns successfully the target EFS inventing such auxiliary predicates via membership and equivalence queries in polynomial time