This book constitutes the refereed proceedings of the 10th International Colloquium on Grammatical Inference, ICGI 2010, held in Valencia, Spain, in September 2010. The 18 revised full papers and 14 revised short papers presented were carefully reviewed and selected from numerous submissions. The topics of the papers presented vary from theoretical results about the learning of different formal language classes (regular, context-free, context-sensitive, etc.) to application papers on bioinformatics, language modelling or software engineering. Furthermore there are two invited papers on the topics grammatical inference and games and molecules, languages, and automata.
Author(s): Simon M. Lucas (auth.), José M. Sempere, Pedro García (eds.)
Series: Lecture Notes in Computer Science 6339 : Lecture Notes in Artificial Intelligence
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2010
Language: English
Pages: 317
Tags: Artificial Intelligence (incl. Robotics); Computation by Abstract Devices; Pattern Recognition; Algorithm Analysis and Problem Complexity; Image Processing and Computer Vision; Mathematical Logic and Formal Languages
Front Matter....Pages -
Grammatical Inference and Games: Extended Abstract....Pages 1-4
Molecules, Languages and Automata....Pages 5-10
Inferring Regular Trace Languages from Positive and Negative Samples....Pages 11-23
Distributional Learning of Some Context-Free Languages with a Minimally Adequate Teacher....Pages 24-37
Learning Context Free Grammars with the Syntactic Concept Lattice....Pages 38-51
Learning Automata Teams....Pages 52-65
Exact DFA Identification Using SAT Solvers....Pages 66-79
Learning Deterministic Finite Automata from Interleaved Strings....Pages 80-93
Learning Regular Expressions from Representative Examples and Membership Queries....Pages 94-108
Splitting of Learnable Classes....Pages 109-121
PAC-Learning Unambiguous k , l -NTS ≤ Languages....Pages 122-134
Bounding the Maximal Parsing Performance of Non-Terminally Separated Grammars....Pages 135-147
CGE: A Sequential Learning Algorithm for Mealy Automata....Pages 148-162
Using Grammar Induction to Model Adaptive Behavior of Networks of Collaborative Agents....Pages 163-177
Transducer Inference by Assembling Specific Languages....Pages 178-188
Sequences Classification by Least General Generalisations....Pages 189-202
A Likelihood-Ratio Test for Identifying Probabilistic Deterministic Real-Time Automata from Positive Data....Pages 203-216
A Local Search Algorithm for Grammatical Inference....Pages 217-229
Polynomial-Time Identification of Multiple Context-Free Languages from Positive Data and Membership Queries....Pages 230-244
Grammatical Inference as Class Discrimination....Pages 245-257
MDL in the Limit....Pages 258-261
Grammatical Inference Algorithms in MATLAB....Pages 262-266
A Non-deterministic Grammar Inference Algorithm Applied to the Cleavage Site Prediction Problem in Bioinformatics....Pages 267-270
Learning PDFA with Asynchronous Transitions....Pages 271-275
Grammar Inference Technology Applications in Software Engineering....Pages 276-279
Hölder Norms and a Hierarchy Theorem for Parameterized Classes of CCG....Pages 280-283
Learning of Church-Rosser Tree Rewriting Systems....Pages 284-287
Generalizing over Several Learning Settings....Pages 288-292
Rademacher Complexity and Grammar Induction Algorithms: What It May (Not) Tell Us....Pages 293-296
Extracting Shallow Paraphrasing Schemata from Modern Greek Text Using Statistical Significance Testing and Supervised Learning....Pages 297-300
Learning Subclasses of Parallel Communicating Grammar Systems....Pages 301-304
Enhanced Suffix Arrays as Language Models: Virtual k -Testable Languages....Pages 305-308
Learning Fuzzy Context-Free Grammar—A Preliminary Report....Pages 309-312
Polynomial Time Identification of Strict Prefix Deterministic Finite State Transducers....Pages 313-316
Back Matter....Pages -
