Polynomial-time inference of arbitrary pattern languages

DOI10.1007/BF03037093zbMath0712.68082MaRDI QIDQ749229

Steffen Lange, Rolf Wiehagen

Publication date: 1991

Published in: New Generation Computing (Search for Journal in Brave)

zbMATH Keywords

inductive inferencemachine learningpolynomial-time complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Probability and inductive logic (03B48)

Related Items (44)

Revisiting Shinohara's algorithm for computing descriptive patterns ⋮ A model of interactive teaching ⋮ Closure properties of pattern languages ⋮ From learning in the limit to stochastic finite learning ⋮ Learning a subclass of regular patterns in polynomial time ⋮ Characterization of language learning front informant under various monotonicity constraints ⋮ Ignoring data may be the only way to learn efficiently ⋮ Inferring descriptive generalisations of formal languages ⋮ Learning pattern languages over groups ⋮ Regular patterns, regular languages and context-free languages ⋮ Regular and context-free pattern languages over small alphabets ⋮ Gold-Style Learning Theory ⋮ Parallelism Increases Iterative Learning Power ⋮ Learning Efficiency of Very Simple Grammars from Positive Data ⋮ On Learning Regular Expressions and Patterns Via Membership and Correction Queries ⋮ Iterative Learning of Simple External Contextual Languages ⋮ Developments from enquiries into the learnability of the pattern languages from positive data ⋮ Discontinuities in pattern inference ⋮ Learning indexed families of recursive languages from positive data: A survey ⋮ Patterns with bounded treewidth ⋮ Monotonic and dual monotonic language learning ⋮ Case-based representation and learning of pattern languages ⋮ Automatic learning of subclasses of pattern languages ⋮ Learnability of automatic classes ⋮ On the power of inductive inference from good examples ⋮ Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries ⋮ Iterative learning of simple external contextual languages ⋮ Learning in the limit with lattice-structured hypothesis spaces ⋮ Variations on U-shaped learning ⋮ U-shaped, iterative, and iterative-with-counter learning ⋮ Learning efficiency of very simple grammars from positive data ⋮ Parallelism increases iterative learning power ⋮ Set-driven and rearrangement-independent learning of recursive languages ⋮ UNAMBIGUOUS MORPHIC IMAGES OF STRINGS ⋮ Learning Pattern Languages over Groups ⋮ 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. ⋮ On the power of incremental learning. ⋮ Incremental concept learning for bounded data mining. ⋮ Inductive inference of approximations for recursive concepts ⋮ Learning erasing pattern languages with queries ⋮ Logic program synthesis from incomplete specifications ⋮ A non-learnable class of E-pattern languages

Cites Work

• Finding patterns common to a set of strings
• Research in the theory of inductive inference by GDR mathematicians - A survey
• On the power of inductive inference from good examples
• Toward a mathematical theory of inductive inference
• Language identification in the limit

This page was built for publication: Polynomial-time inference of arbitrary pattern languages