Abstract
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 language | Undefined/Unknown |
|---|---|
| Title of host publication | Proceedings of ALT |
| Editors | M. Kanazawa et al |
| Place of Publication | Canberra, Australia |
| Publisher | Springer |
| Pages | 11-30 |
| Number of pages | 20 |
| Volume | 6331 LNAI |
| Publication status | Published - 1 Oct 2010 |