Grammatical Inference: Algorithms and Applications: 9th International Colloquium, ICGI 2008 Saint-Malo, France, September 22-24, 2008 Proceedings

✍ Scribed by Dana Angluin, Leonor Becerra-Bonache (auth.), Alexander Clark, François Coste, Laurent Miclet (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2008
• Tongue: English
• Leaves: 313
• Series: Lecture Notes in Computer Science 5278 : Lecture Notes in Artificial Intelligence
• Edition: 1
• Category: Library

✦ Synopsis

This book constitutes the refereed proceedings of the 9th International Colloquium on Grammatical Inference, ICGI 2008, held in Saint-Malo, France, in September 2008.

The 21 revised full papers and 8 revised short papers presented were carefully reviewed and selected from 36 submissions. The topics of the papers presented vary from theoretical results of learning algorithms to innovative applications of grammatical inference, and from learning several interesting classes of formal grammars to applications to natural language processing.

✦ Table of Contents

Front Matter....Pages -
Learning Meaning Before Syntax....Pages 1-14
Schema-Guided Induction of Monadic Queries....Pages 15-28
A Polynomial Algorithm for the Inference of Context Free Languages....Pages 29-42
Learning Languages from Bounded Resources: The Case of the DFA and the Balls of Strings....Pages 43-56
Relevant Representations for the Inference of Rational Stochastic Tree Languages....Pages 57-70
Learning Commutative Regular Languages....Pages 71-83
Learning Left-to-Right and Right-to-Left Iterative Languages....Pages 84-97
Learning Bounded Unions of Noetherian Closed Set Systems Via Characteristic Sets....Pages 98-110
A Learning Algorithm for Multi-dimensional Trees, or: Learning Beyond Context-Freeness....Pages 111-124
On Learning Regular Expressions and Patterns Via Membership and Correction Queries....Pages 125-138
State-Merging DFA Induction Algorithms with Mandatory Merge Constraints....Pages 139-153
Using Multiplicity Automata to Identify Transducer Relations from Membership and Equivalence Queries....Pages 154-162
Towards Feasible PAC-Learning of Probabilistic Deterministic Finite Automata....Pages 163-174
Learning Context-Sensitive Languages from Linear Structural Information....Pages 175-186
Polynomial Time Probabilistic Learning of a Subclass of Linear Languages with Queries....Pages 187-199
How to Split Recursive Automata....Pages 200-212
A Note on the Relationship between Different Types of Correction Queries....Pages 213-223
Unsupervised Learning of Probabilistic Context-Free Grammar using Iterative Biclustering....Pages 224-237
Polynomial Distinguishability of Timed Automata....Pages 238-251
Evaluation and Comparison of Inferred Regular Grammars....Pages 252-265
Identification in the Limit of k , l -Substitutable Context-Free Languages....Pages 266-279
Learning Subclasses of Pure Pattern Languages....Pages 280-282
Which Came First, the Grammar or the Lexicon?....Pages 283-285
Learning Node Label Controlled Graph Grammars (Extended Abstract)....Pages 286-288
Inference of Uniquely Terminating EML....Pages 289-291
Estimating Graph Parameters Using Graph Grammars....Pages 292-294
Learning of Regular ω -Tree Languages....Pages 295-297
Inducing Regular Languages Using Grammar-Based Classifier System....Pages 298-300
Problems with Evaluation of Unsupervised Empirical Grammatical Inference Systems....Pages 301-303
Back Matter....Pages -

✦ Subjects

Artificial Intelligence (incl. Robotics); Mathematical Logic and Formal Languages; Logics and Meanings of Programs