This book constitutes the refereed proceedings of the 7th International Colloquium on Grammatical Inference, ICGI 2004, held in Athens, Greece in October 2004.
The 20 revised full papers and 8 revised poster papers presented together with 3 invited contributions were carefully reviewed and selected from 45 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 estimations of probabilistic grammars.
Author(s): Dana Angluin (auth.), Georgios Paliouras, Yasubumi Sakakibara (eds.)
Series: Lecture Notes in Computer Science 3264 : Lecture Notes in Artificial Intelligence
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2004
Language: English
Pages: 296
Tags: Artificial Intelligence (incl. Robotics); Mathematical Logic and Formal Languages; Logics and Meanings of Programs
Front Matter....Pages -
Learning and Mathematics....Pages 1-2
Learning Finite-State Models for Machine Translation....Pages 3-15
The Omphalos Context-Free Grammar Learning Competition....Pages 16-27
Mutually Compatible and Incompatible Merges for the Search of the Smallest Consistent DFA....Pages 28-39
Faster Gradient Descent Training of Hidden Markov Models, Using Individual Learning Rate Adaptation....Pages 40-52
Learning Mild Context-Sensitiveness: Toward Understanding Children’s Language Learning....Pages 53-64
Learnability of Pregroup Grammars....Pages 65-76
A Markovian Approach to the Induction of Regular String Distributions....Pages 77-90
Learning Node Selecting Tree Transducer from Completely Annotated Examples....Pages 91-102
Identifying Clusters from Positive Data....Pages 103-114
Introducing Domain and Typing Bias in Automata Inference....Pages 115-126
Analogical Equations in Sequences: Definition and Resolution....Pages 127-138
Representing Languages by Learnable Rewriting Systems....Pages 139-150
A Divide-and-Conquer Approach to Acquire Syntactic Categories....Pages 151-162
Grammatical Inference Using Suffix Trees....Pages 163-174
Learning Stochastic Finite Automata....Pages 175-186
Navigation Pattern Discovery Using Grammatical Inference....Pages 187-198
A Corpus-Driven Context-Free Approximation of Head-Driven Phrase Structure Grammar....Pages 199-210
Partial Learning Using Link Grammars Data....Pages 211-222
eg-GRIDS: Context-Free Grammatical Inference from Positive Examples Using Genetic Search....Pages 223-234
The Boisdale Algorithm – An Induction Method for a Subclass of Unification Grammar from Positive Data....Pages 235-247
Learning Stochastic Deterministic Regular Languages....Pages 248-259
Polynomial Time Identification of Strict Deterministic Restricted One-Counter Automata in Some Class from Positive Data....Pages 260-272
Learning Syntax from Function Words....Pages 273-274
Running FCRPNI in Efficient Time for Piecewise and Right Piecewise Testable Languages....Pages 275-276
Extracting Minimum Length Document Type Definitions Is NP-Hard....Pages 277-278
Learning Distinguishable Linear Grammars from Positive Data....Pages 279-280
Extending Incremental Learning of Context Free Grammars in Synapse....Pages 281-282
Identifying Left-Right Deterministic Linear Languages....Pages 283-284
Efficient Learning of k -Reversible Context-Free Grammars from Positive Structural Examples....Pages 285-287
An Analysis of Examples and a Search Space for PAC Learning of Simple Deterministic Languages with Membership Queries....Pages 288-289
Back Matter....Pages -
