salle A. Turing CE4
16 January 2014 - 16h00
Learning Regular Languages over Large Alphabets
by Irini-Eleftheria Mens from Verimag
Abstract: In this work we developed a generic algorithm for learning regular languages defined over a large alphabet Σ. Such an alphabet can be infinite, like N or R or just so large that it is impossible or impractical to treat it in an enumerative way. The obvious solution is to use a symbolic representation where transitions are labeled by predicates which are applicable to the alphabet in question. Learning algorithms infer an automaton from a infinite set of words (the sample) for which membership is known. Over small alphabets, the sample should include all shortest words that lead to each state and all their Σ-continuations. Over large alphabets this is not a practical option and as an alternative we develop a symbolic learning algorithm over symbolic words which are only partially backed up by the sample.
