This book explains advanced issues in grammatical inference. The first three chapters of the book deal with issues regarding the theoretical learning framework. The remaining chapters focus on the main classes of formal languages according to Chomsky"s hierarchy: the regular languages and the context-free languages. The topics chosen are of foundational interest, and they are relatively mature, with established results, algorithms and conclusions.The book will be of value to researchers in computer science, bioinformatics, robotics, and computational linguistics. Some knowledge of theoretical computer science, including formal language theory and automata theory, formal grammars, and algorithmics, is a prerequisite for reading this book.
Introduction.- Gold-Style Learning Theory.- Efficiency in the Identification in the Limit Learning Paradigm.- Learning Grammars and Automata with Queries.- On the Inference of Finite State Automata from Positive and Negative Data.- Learning Probability Distributions Generated by Finite-State Machines.- Distributional Learning of Context-Free and Multiple.- Context-Free Grammars.- Learning Tree Languages.- Learning the Language of Biological Sequences.
