Inference of !-languages from pre$xes
J. C. Janodet · 2004
B+ uchi automata are used to recognize languages of in$nite strings. Such languages have been introduced to describe the behavior of real-time systems or in$nite games. The question of inferring them from in$nite examples has already been studied, but it may seem more reasonable to believe that the data from which we want to learn is a set of $nite strings, namely the pre$xes of accepted or rejected in$nite strings. We describe the problems of identi$cation in the limit and polynomial identi$cation in the limit from given data associated to di2erent interpretations of these pre$xes: a positive pre$x is universal (respectively existential) when all the in$nite strings of which it is a pre$x are in the language (respectively when at least one is); the same applies to the negative pre$xes. We prove that the classes of regular !-languages (those recognized by B+ automata) and of deterministic !-languages (those recognized by deterministic B+ uchi automata) are not identi$able in the limit, whatever interpretation for the pre$xes is taken. We give a polynomial algorithm that identi$es the class of safe languages from positive existential pre$xes and negative universal pre$xes. We show that this class is maximal for polynomial identi$cation in the limit from given data, in the sense that no superclass can even be identi$ed in the limit. c 2003 Elsevier B.V. All rights reserved. MSC: 68T05