Grammatical Inference: Algorithms and Applications: 8th International Colloquium, ICGI 2006, Tokyo, Japan, September 20-22, 2006. Proceedings

✍ Scribed by Yuji Matsumoto (auth.), Yasubumi Sakakibara, Satoshi Kobayashi, Kengo Sato, Tetsuro Nishino, Etsuji Tomita (eds.)

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

✦ Synopsis

This book constitutes the refereed proceedings of the 8th International Colloquium on Grammatical Inference, ICGI 2006, held in Tokyo, Japan in September 2006.

The 25 revised full papers and 8 revised short papers presented together with 2 invited contributions were carefully reviewed and selected from 44 submissions. The topics of the papers presented range 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 -
Parsing Without Grammar Rules....Pages 1-6
Classification of Biological Sequences with Kernel Methods....Pages 7-18
Identification in the Limit of Systematic-Noisy Languages....Pages 19-31
Ten Open Problems in Grammatical Inference....Pages 32-44
Polynomial-Time Identification of an Extension of Very Simple Grammars from Positive Data....Pages 45-58
PAC-Learning Unambiguous NTS Languages....Pages 59-71
Incremental Learning of Context Free Grammars by Bridging Rule Generation and Search for Semi-optimum Rule Sets....Pages 72-83
Variational Bayesian Grammar Induction for Natural Language....Pages 84-96
Stochastic Analysis of Lexical and Semantic Enhanced Structural Language Model....Pages 97-111
Using Pseudo-stochastic Rational Languages in Probabilistic Grammatical Inference....Pages 112-124
Learning Analysis by Reduction from Positive Data....Pages 125-136
Inferring Grammars for Mildly Context Sensitive Languages in Polynomial-Time....Pages 137-147
Planar Languages and Learnability....Pages 148-160
A Unified Algorithm for Extending Classes of Languages Identifiable in the Limit from Positive Data....Pages 161-174
Protein Motif Prediction by Grammatical Inference....Pages 175-187
Grammatical Inference in Practice: A Case Study in the Biomedical Domain....Pages 188-200
Inferring Grammar Rules of Programming Language Dialects....Pages 201-213
The Tenjinno Machine Translation Competition....Pages 214-226
Large Scale Inference of Deterministic Transductions: Tenjinno Problem 1....Pages 227-239
A Discriminative Model of Stochastic Edit Distance in the Form of a Conditional Transducer....Pages 240-252
Learning n-Ary Node Selecting Tree Transducers from Completely Annotated Examples....Pages 253-267
Learning Multiplicity Tree Automata....Pages 268-280
Learning DFA from Correction and Equivalence Queries....Pages 281-292
Using MDL for Grammar Induction....Pages 293-306
Characteristic Sets for Inferring the Unions of the Tree Pattern Languages by the Most Fitting Hypotheses....Pages 307-319
Learning Deterministic DEC Grammars Is Learning Rational Numbers....Pages 320-326
Iso-array Acceptors and Learning....Pages 327-339
A Merging States Algorithm for Inference of RFSAs ....Pages 340-341
Query-Based Learning of XPath Expressions....Pages 342-343
Learning Finite-State Machines from Inexperienced Teachers....Pages 344-345
Suprasymbolic Grammar Induction by Recurrent Self-Organizing Maps....Pages 346-348
Graph-Based Structural Data Mining in Cognitive Pattern Interpretation....Pages 349-350
Constructing Song Syntax by Automata Induction....Pages 351-353
Learning Reversible Languages with Terminal Distinguishability....Pages 354-355
Grammatical Inference for Syntax-Based Statistical Machine Translation....Pages 356-357
Back Matter....Pages -

✦ Subjects

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