Grammatical Inference: Algorithms and Applications: 7th International Colloquium, ICGI 2004, Athens, Greece, October 11-13, 2004. Proceedings (Lecture ... / Lecture Notes in Artificial Intelligence)

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. 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 - The 7th International Colloquium on Grammatical Inference (ICGI 2004) was held in the National Centre for Scientific Research "Demokritos", Athens, Greece on October 11-13, 2004. ICGI 2004 was the seventh in a series of successful biennial international conferences in the area of grammatical inference. Previous meetings were held in Essex, UK; Alicante, Spain; Montpellier, France; Ames, Iowa, USA; Lisbon, Portugal; and Amsterdam, The Netherlands. This series of conferences seeks to provide a forum for the presentation and discussion of original research papers on all aspects of grammatical inference. Grammatical inference, the study of learning grammars from data, is an established research field in artificial intelligence, dating back to the 1960s, and has been extensively addressed by researchers in automata theory, language acquisition, computational linguistics, machine learning, pattern recognition, computational learning theory and neural networks. ICGI 2004 emphasized the multidisciplinary nature of the research field and the diverse domains in which grammatical inference is being applied, such as natural language acquisition, computational biology, structural pattern recognition, information retrieval, Web mining, text processing, data compression and adaptive intelligent agents. We received 45 high-quality papers from 19 countries. The papers were - viewed by at least two - in most cases three - reviewers. In addition to the 20 full papers, 8 short papers that received positive comments from the reviewers were accepted, and they appear in a separate section of this volume. The topics of the accepted papers vary 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