Grammatical Inference: Learning Automata and GrammarsCambridge University Press, 1 Nis 2010 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. |
İçindekiler
1 | |
The data and some applications | 27 |
Basic stringology | 45 |
Representing languages | 70 |
Representing distributions over strings with automata and grammars | 86 |
About combinatorics | 116 |
Identifying languages | 143 |
Learning from text | 173 |
Text learners | 217 |
Informed learners | 237 |
Learning with queries | 269 |
Artificial intelligence techniques | 281 |
Learning contextfree grammars | 300 |
Learning probabilistic finite automata | 329 |
Estimating the probabilities | 357 |
Learning transducers | 372 |
Diğer baskılar - Tümünü görüntüle
Sık kullanılan terimler ve kelime öbekleri
accepted algorithm allows alphabet alternative answer associated automata automaton better BLUE bounded build called Chapter characteristic closed complexity compute concerning consider consistent construction contains context-free grammars correct corresponding count defined Definition denote described deterministic distance distribution DPFA encoding equivalence example exists fact Figure finite first formal function give given going grammar grammatical inference Higuera idea identifiable ifdef important initial Input interesting introduced issues labelled language learning least length limit linear machine means merge multiset needed Note Notice obtained operations Oracle Output parse pattern polynomial positive possible presentation probabilistic probability problem Proof proposed Prove queries question reasons regular relation represented rules sample situation strings structure studied Suppose symbol task Theorem transducer transition tree usually