Inferring non deterministic finite automata, thanks to ambiguity management, owing to application in bioinformatics:
This work (realized during my PhD thesis) concerned Regular Grammar inference under the form of Nondeterministic Automata. It took place in the  Irisa laboratory, in the Symbiose Project and under the direction of Jacques Nicolas and François Coste.
Keywords : Machine learning, regular grammatical inference, non deterministic automata, bioinformatics.
Summary :
This project aimed at adapting regular grammatical inference methods to the needs observed in the research field of bioinformatics; especially, for the application called "pattern discovery". In this framework, the goal is to characterize a set of biological sequences with a common function thanks to a model. This model has to be discovered  automatically from examples of sequences possessing the function and, if available, from counter-examples (i.e. sequences without the function).

The models we consider are non deterministic finite automata. The inference of these models has not been studied much. However they can be considered as more interesting to represent sets of biological sequences than the deterministic automata usually considered in the regular grammatical inference field. The work we realized brought to the field :

• an efficient method to detect the compatibility of the inferred automata with the counter-examples [CF00]
• the formalization of the search space for a hierarchy of subclasses of nondeterministic automata [CF03a]
• the reduction of the search space to unambiguous automata together with an inference algorithm for these automata [CF01,CF03c]
• tools for the formalization and the introduction of background knowledge into inference [CF03b,CFKH04].

First tries to tackle biological data with nondeterministic automata inference have been published in [CKIFD04].