Efficiency in the identification in the limit learning paradigm

DOI10.1007/978-3-662-48395-4_2MaRDI QIDQ2963593zbMATH OpenOpenAlexFDO

Authors Rémi Eyraud, Jeffrey Heinz, Ryo Yoshinaka

Publication date 15 February 2017

Published in Topics in Grammatical Inference (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-48395-4_2

Mathematics Subject Classification ID

Computational learning theory (68Q32) Grammars and rewriting systems (68Q42)

Recommendations

• Can learning in the limit be done efficiently?
• Learning efficiency of very simple grammars from positive data
• Learning Efficiency of Very Simple Grammars from Positive Data
• Learning and classifying
• Learning and classifying

Cites work

• scientific article; zbMATH DE number 5957212 (Why is no real title available?)
• A solution of the syntactical induction-inference problem for regular languages
• A theory of the learnable
• Characteristic sets for polynomial grammatical inference
• Distributional learning of parallel multiple context-free grammars
• Efficient learning of context-free grammars from positive structural examples
• Efficient learning of multiple context-free languages with multidimensional substitutability from positive data
• Finding patterns common to a set of strings
• From learning in the limit to stochastic finite learning
• Inductive inference of formal languages from positive data
• LARS: a learning algorithm for rewriting systems
• Language identification in the limit
• Learnability and the Vapnik-Chervonenkis dimension
• Learning Simple Concepts under Simple Distributions
• Learning efficiency of very simple grammars from positive data
• Learning register automata: from languages to program structures
• Learning trees from strings: a strong learning algorithm for some context-free grammars
• On multiple context-free grammars
• On polynomial-time learnability in the limit of strictly deterministic automata
• Polynomial identification in the limit of substitutable context-free languages
• Polynomial time learning of simple deterministic languages via queries and a representative sample
• Polynomial-time identification of very simple grammars from positive data.
• Three models for the description of language
• Toward a mathematical theory of inductive inference
• Tutorial on practical prediction theory for classification
• VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states

Cited in

(5)

• Robust identification in the limit from incomplete positive data
• Can learning in the limit be done efficiently?
• Learning context-free grammars from positive data and membership queries
• A fixed rehearsal capacity interpretation of limits on absolute identification performance
• Identification Rate, Search and Memory Complexity Tradeoff: Fundamental Limits

This page was built for publication: Efficiency in the identification in the limit learning paradigm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2963593)