Affiliations: Telstra Research Laboratories, 770 Blackburn Rd Clayton, Melbourne, Victoria 3127, Australia E-mail: [email protected] | IRISA, Campus de Beaulieu, 35042 Rennes, France E-mail: [email protected] | Tilburg University, Postbus 90153, 5000LE, Tilburg, The Netherlands E-mail: [email protected]
Note: [] Corresponding author.
Abstract: This paper describes the Omphalos Context-Free Language Learning Competition held as part of the International Colloquium on Grammatical Inference 2004. After the success of the Abbadingo Competition on the better known task of learning regular languages, the competition was created in an effort to promote the development of new and better grammatical inference algorithms for context-free languages, to provide a forum for the comparison of different grammatical inference algorithms and to gain insight into the current state-of-the-art of context-free grammatical inference algorithms. This paper discusses design issues and decisions made when creating the competition, leading to the introduction of a new complexity measure developed to estimate the difficulty of learning a context-free grammar. It presents also the results of the competition and lessons learned.
