Grammatical Inference
Learning Automata and Grammars

The first book to present the basic techniques and main results of this expanding field of research.

Colin de la Higuera (Author)

9780521763165, Cambridge University Press

Hardback, published 1 April 2010

432 pages, 170 b/w illus. 25 tables 1 music example 160 exercises
25.4 x 18 x 2.6 cm, 0.9 kg

'… this book raises important questions about learning grammars …' Computing Reviews

The problem of inducing, learning or inferring grammars has been studied for decades, but only in recent years has grammatical inference emerged as an independent field with connections to many scientific disciplines, including bio-informatics, computational linguistics and pattern recognition. This book meets the need for a comprehensive and unified summary of the basic techniques and results, suitable for researchers working in these various areas. In Part I, the objects of use for grammatical inference are studied in detail: strings and their topology, automata and grammars, whether probabilistic or not. Part II carefully explores the main questions in the field: What does learning mean? How can we associate complexity theory with learning? In Part III the author describes a number of techniques and algorithms that allow us to learn from text, from an informant, or through interaction with the environment. These concern automata, grammars, rewriting systems, pattern languages or transducers.

Preface
Acknowledgements
1. Introduction
2. The data and some applications
Part I. The Tools: 3. Basic stringology
4. Representing languages
5. Representing distributions over strings with automata and grammars
6. About combinatorics
Part II. What Does Learning a Language Mean?: 7. Identifying languages
8. Learning from text
9. Active learning
10. Learning distributions over strings
Part III. Learning Algorithms and Techniques: 11. Text learners
12. Informed learners
13. Learning with queries
14. Artificial intelligence techniques
15. Learning context-free grammars
16. Learning probabilistic finite automata
17. Estimating the probabilities
18. Learning transducers
19. A very small conclusion
References
Index.

Subject Areas: Machine learning [UYQM], Natural language & machine translation [UYQL]