Towards General Algorithms for Grammatical Inference

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

21 Citations (Scopus)


Many algorithms for grammatical inference can be viewed as instances of a more general algorithm which maintains a set of primitive elements, which distributionally define sets of strings, and a set of features or tests that constrain various inference rules. Using this general framework, which we cast as a process of logical inference, we re-analyse Angluin's famous sc lstar algorithm and several recent algorithms for the inference of context-free grammars and multiple context-free grammars. Finally, to illustrate the advantages of this approach, we extend it to the inference of functional transductions from positive data only, and we present a new algorithm for the inference of finite state transducers.
Original languageUndefined/Unknown
Title of host publicationProceedings of ALT
EditorsM. Kanazawa et al
Place of PublicationCanberra, Australia
Number of pages20
Volume6331 LNAI
Publication statusPublished - 1 Oct 2010

Cite this