Title: Grammatical Inference: Theory and Techniques

Abstract:

Many objects can be represented as strings over some alphabet, for example, DNA sequences, natural language sentences or sequences of machine events. Sometimes, we have examples of strings from a particular category X, but we do not have a complete description of X. The task of learning categories of strings (i.e. formal languages) from a given finite set of example strings is known as grammatical inference.  More formally, grammatical inference is the task of learning, under some learning model M, a binary classifier G (i.e. a language representation) that describes the target language L which is an element of a language class C (i.e. the hypothesis space), given examples from L and, optionally, additional information on L (e.g. negative data, structured data, queries). 

This talk is divided in two parts. First, the theoretical foundations of this field are presented by highlighting what is undecidable, intractable or tractable under different scenarios. Then, the techniques used in grammatical inference algorithms are discussed.