Learning a subclass of regular patterns in polynomial time

DOI10.1016/j.tcs.2006.07.044zbMath1153.68021OpenAlexW2126682116WikidataQ125057253 ScholiaQ125057253MaRDI QIDQ860829

Frank Stephan, John Case, Thomas Zeugmann, Sanjay Jain, K. Ruediger Reischuk

Publication date: 9 January 2007

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

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

zbMATH Keywords

average-case analysispattern languagesalgorithmic learningprobabilistically exact learning

Mathematics Subject Classification ID

Computational learning theory (68Q32) Formal languages and automata (68Q45)

Related Items

Automatic learning of subclasses of pattern languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial-time inference of arbitrary pattern languages
• A guided tour of Chernoff bounds
• Finding patterns common to a set of strings
• Learning elementary formal systems
• Finding tree patterns consistent with positive and negative examples using queries
• Lange and Wiehagen's pattern language learning algorithm: An average-case analysis with respect to its total learning time
• An average-case optimal one-variable pattern language learner
• On learning unions of pattern languages and tree patterns in the mistake bound model.
• Incremental concept learning for bounded data mining.
• Theory of Formal Systems. (AM-47)
• A theory of the learnable
• Inductive Logic Programming: Theory and methods
• Learning Theory
• STACS 2004
• Language identification in the limit
• Inductive inference of unbounded unions of pattern languages from positive data
• Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries
• Stochastic finite learning of the pattern languages
• On exact learning of unordered tree patterns
• Predictive learning models for concept drift