Grammar Induction

A definition

Grammar Induction, also known as Grammatical Inference, is a particular instance of Inductive Learning which can be formulated as the task of discovering common structures in examples which are supposed to be generated by the same process. In this case, the set of examples, also called positive sample, is usually a set of strings defined on a specific alphabet. A negative sample, that is a set of strings not belonging to the target language, may also help the induction process.

This problem has been studied as early as the growth of the theory of formal grammars. It has an obvious theoritical interest and also an important range of applications, in particular in the fields of Identification of Sequential Processes, Pattern Recognition, Speech and Natural Language Processing . The theoretical complexity of this problem is now well established and many empirical algorithms have been devised.

Grammar Induction Tutorials

Grammar Induction References

Events

ICGI'08, 9th International Colloquium on Grammatical Inference, St Malo, Britanny, France, September 22-24, 2008.

A workshop on Challenges and Applications of Grammar Induction in conjunction with the International Conference on Machine Learning (ICML'07), Oregon State University, June 20 - June 24, 2007

ICGI'06, 8th International Colloquium on Grammatical Inference, Tokyo (Japan), September 2006.

A tutorial on Grammar Induction: Techniques and Theory was held at ICML'06, Carnegie Mellon University in Pittsburgh, Pennsylvania, USA on June 25, 2006.

A workshop on Grammatical Inference Applications: Successes and Future Challenges was held at IJCAI'05, Edinburgh, Scotland on July 31, 2005.

ICGI'04, 7th International Colloquium on Grammatical Inference, Athens (Greece), October 2004.

A workshop and tutorial on Learning Context-Free Grammars, was held at ECML/PKDD 2003, Dubrovnik (Croatia), September 2003.

ICGI'02, 6th International Colloquium on Grammatical Inference, Amsterdam (Netherlands), September 2002.

ICGI'00, 5th International Colloquium on Grammatical Inference, Lisbon (Portugal), September 2000.

ICGI'98, 4th International Colloquium on Grammatical Inference, Ames (Iowa), July 1998.

A workshop on Automata Induction, Grammatical Inference, and Language Acquisition was held at the ICML'97 conference.

ICGI'96, 3rd International Colloquium on Grammatical Inference, Montpellier (France), September 1996.

ICGI'94, 2nd International Colloquium on Grammatical Inference, Alicante (Spain), September 1994.

ICGI'93, 1st International Colloquium on Grammatical Inference, University of Essex, Colchester (UK), 1993.

Competitions and Benchmarks

The Tenjinno Machine Translation Competition, 2006.

Omphalos, a context-free language learning competition, 2004.

Learning DFA from Noisy Samples, a contest for GECCO 2004.

Gowachin, the successor of Abbadingo.

Abbadingo ONE, a DFA learning competition.