Learning efficiency of very simple grammars from positive data

DOI10.1016/j.tcs.2009.01.012zbMath1167.68028MaRDI QIDQ1017659

Ryo Yoshinaka

Publication date: 12 May 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.01.012

zbMATH Keywords

grammatical inference; identification in the limit; learning efficiency; very simple grammars

Mathematics Subject Classification ID

68Q32: Computational learning theory

68Q42: Grammars and rewriting systems

Related Items

Iterative learning of simple external contextual languages, Efficiency in the Identification in the Limit Learning Paradigm, Difficulties in Forcing Fairness of Polynomial Time Inductive Inference

Cites Work

• Unnamed Item
• Polynomial-time inference of arbitrary pattern languages
• Grammatical inference for even linear languages based on control sets
• Finding patterns common to a set of strings
• Two decidability results for deterministic pushdown automata
• Characteristic sets for polynomial grammatical inference
• Polynomial-time identification of very simple grammars from positive data.
• On polynomial-time learnability in the limit of strictly deterministic automata
• Learning Efficiency of Very Simple Grammars from Positive Data
• Polynomial-Time Identification of an Extension of Very Simple Grammars from Positive Data
• Inference of Reversible Languages
• Ignoring data may be the only way to learn efficiently
• Grammatical Inference: Algorithms and Applications