Grammatical Inference: Algorithms and Applications

The Sixth International Colloquium on Grammatical Inference (ICGI2002) was held in Amsterdam on September 23-25th, 2002. ICGI2002 was the sixth in a series of successful biennial international conferenceson the area of grammatical inference. Previous meetings were held in Essex, U.K.; Alicante, Spain; Mo- pellier, France; Ames, Iowa, USA; Lisbon, Portugal. This series of meetings seeks to provide a forum for the presentation and discussion of original research on all aspects of grammatical inference. Gr- matical inference, the process of inferring grammars from given data, is a ?eld that not only is challenging from a purely scienti?c standpoint but also ?nds many applications in real-world problems. Despite the fact that grammatical inference addresses problems in a re- tively narrow area, it uses techniques from many domains, and is positioned at the intersection of a number of di?erent disciplines. Researchers in grammatical inference come from ?elds as diverse as machine learning, theoretical computer science, computational linguistics, pattern recognition, and arti?cial neural n- works. From a practical standpoint, applications in areas like natural language - quisition, computational biology, structural pattern recognition, information - trieval, text processing, data compression and adaptive intelligent agents have either been demonstrated or proposed in the literature. The technical program included the presentation of 23 accepted papers (out of 41 submitted). Moreover, for the ?rst time a software presentation was or- nized at ICGI. Short descriptions of the corresponding software are included in these proceedings, too.

Inhalt

Contributions.- Inference of Sequential Association Rules Guided by Context-Free Grammars.- PCFG Learning by Nonterminal Partition Search.- Inferring Subclasses of Regular Languages Faster Using RPNI and Forbidden Configurations.- Beyond EDSM.- Consistent Identification in the Limit of Rigid Grammars from Strings Is NP-hard.- Some Classes of Regular Languages Identifiable in the Limit from Positive Data.- Learning Probabilistic Residual Finite State Automata.- Fragmentation: Enhancing Identifiability.- On Limit Points for Some Variants of Rigid Lambek Grammars.- Generalized Stochastic Tree Automata for Multi-relational Data Mining.- On Sufficient Conditions to Identify in the Limit Classes of Grammars from Polynomial Time and Data.- Stochastic Grammatical Inference with Multinomial Tests.- Learning Languages with Help.- Incremental Learning of Context Free Grammars.- Estimating Grammar Parameters Using Bounded Memory.- Stochastic k-testable Tree Languages and Applications.- Fast Learning from Strings of 2-Letter Rigid Grammars.- Learning Locally Testable Even Linear Languages from Positive Data.- Inferring Attribute Grammars with Structured Data for Natural Language Processing.- A PAC Learnability of Simple Deterministic Languages.- On the Learnability of Hidden Markov Models.- Shallow Parsing Using Probabilistic Grammatical Inference.- Learning of Regular Bi-? Languages.- Software Descriptions.- The EMILE 4.1 Grammar Induction Toolbox.- Software for Analysing Recurrent Neural Nets That Learn to Predict Non-regular Languages.- A Framework for Inductive Learning of Typed-Unification Grammars.- A Tool for Language Learning Based on Categorial Grammars and Semantic Information.- 'NAIL': Artificial Intelligence Software for Learning Natural Language.- Lyrebird(TM): Developing Spoken Dialog Systems Using Examples.- Implementing Alignment-Based Learning.