Grammatical Inference: Algorithms and Applications: 5th International Colloquium, ICGI 2000, Lisbon, Portugal, September 11-13, 2000. Proceedings

✍ Scribed by Francisco Casacuberta (auth.), Arlindo L. Oliveira (eds.)

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

✦ Synopsis

This book constitutes the refereed proceedings of the 5th International Colloquium on Grammatical Inference, ICGI 2000, held in Lisbon, Portugal in September 2000. The 24 revised full papers presented were carefully reviewed and selected from 35 submissions. The papers address topics like machine learning, automata, theoretical computer science, computational linguistics, pattern recognition, artificial neural networks, natural language acquisition, computational biology, information retrieval, text processing, and adaptive intelligent agents.

✦ Table of Contents

Front Matter....Pages -
Inference of Finite-State Transducers by Using Regular Grammars and Morphisms....Pages 1-14
Computational Complexity of Problems on Probabilistic Grammars and Transducers....Pages 15-24
Efficient Ambiguity Detection in C -NFA....Pages 25-38
Learning Regular Languages Using Non Deterministic Finite Automata....Pages 39-50
Smoothing Probabilistic Automata: An Error-Correcting Approach....Pages 51-64
Inferring Subclasses of Contextual Languages....Pages 65-74
Permutations and Control Sets for Learning Non-regular Language Families....Pages 75-88
On the Complexity of Consistent Identification of Some Classes of Structure Languages....Pages 89-102
Computation of Substring Probabilities in Stochastic Grammars....Pages 103-114
A Comparative Study of Two Algorithms for Automata Identification....Pages 115-126
The Induction of Temporal Grammatical Rules from Multivariate Time Series....Pages 127-140
Identification in the Limit with Probability One of Stochastic Deterministic Finite Automata....Pages 141-156
Iterated Transductions and Efficient Learning from Positive Data: A Unifying View....Pages 157-170
An Inverse Limit of Context-Free Grammars – A New Approach to Identifiability in the Limit....Pages 171-185
Synthesizing Context Free Grammars from Sample Strings Based on Inductive CYK Algorithm....Pages 186-195
Combination of Estimation Algorithms and Grammatical Inference Techniques to Learn Stochastic Context-Free Grammars....Pages 196-206
On the Relationship between Models for Learning in Helpful Environments....Pages 207-220
Probabilistic k -Testable Tree Languages....Pages 221-228
Learning Context-Free Grammars from Partially Structured Examples....Pages 229-240
Identification of Tree Translation Rules from Examples....Pages 241-255
Counting Extensional Differences in BC-Learning....Pages 256-269
Constructive Learning of Context-Free Languages with a Subpansive Tree ....Pages 270-283
A Polynomial Time Learning Algorithm of Simple Deterministic Languages via Membership Queries and a Representative Sample....Pages 284-297
Improve the Learning of Subsequential Transducers by Using Alignments and Dictionaries....Pages 298-311
Back Matter....Pages -

✦ Subjects

Artificial Intelligence (incl. Robotics); Mathematical Logic and Formal Languages; Pattern Recognition; Algorithm Analysis and Problem Complexity