Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries

DOI10.1016/S0304-3975(00)00136-5zbMath0976.68085WikidataQ126778400 ScholiaQ126778400MaRDI QIDQ5941371

Angelika Steger, Erlebach, Thomas, Peter Rossmanith, Thomas Zeugmann, Hans Stadtherr

Publication date: 20 August 2001

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

zbMATH Keywords

parallelizationaverage-case analysisinductive learningone-variable pattern languages

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Related Items (14)

Revisiting Shinohara's algorithm for computing descriptive patterns ⋮ Optimization in telecommunication networks ⋮ From learning in the limit to stochastic finite learning ⋮ Learning a subclass of regular patterns in polynomial time ⋮ Regular patterns, regular languages and context-free languages ⋮ Developments from enquiries into the learnability of the pattern languages from positive data ⋮ Learning indexed families of recursive languages from positive data: A survey ⋮ Learnability of automatic classes ⋮ Unnamed Item ⋮ Finitely distinguishable erasing pattern languages ⋮ An average-case optimal one-variable pattern language learner ⋮ Unnamed Item ⋮ On learning unions of pattern languages and tree patterns in the mistake bound model. ⋮ Learning erasing pattern languages with queries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial-time inference of arbitrary pattern languages
• Prudence and other conditions on formal language learning
• Identification of pattern languages from examples and queries
• A note on the two-variable pattern-finding problem
• Avoidable patterns in strings of symbols
• Finding patterns common to a set of strings
• Lange and Wiehagen's pattern language learning algorithm: An average-case analysis with respect to its total learning time
• Queries and concept learning
• A theory of the learnable
• Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones
• On the complexity of inductive inference
• Inductive inference of formal languages from positive data
• Ignoring data may be the only way to learn efficiently
• Inclusion is undecidable for pattern languages
• Set-driven and rearrangement-independent learning of recursive languages
• Parallelism in random access machines
• Language identification in the limit
• Inductive inference of unbounded unions of pattern languages from positive data

This page was built for publication: Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries