A non-learnable class of E-pattern languages

DOI10.1016/j.tcs.2005.10.017zbMath1086.68116OpenAlexW2080895803MaRDI QIDQ817836

Daniel Reidenbach

Publication date: 20 March 2006

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

Full work available at URL: https://figshare.com/articles/A_non-learnable_class_of_E-pattern_languages/9401876

zbMATH Keywords

learning theoryinductive inferencepattern languages

Mathematics Subject Classification ID

Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Pattern recognition, speech recognition (68T10)

Related Items (24)

A parameterized study of maximum generalized pattern matching problems ⋮ Closure properties of pattern languages ⋮ Inferring descriptive generalisations of formal languages ⋮ Learning pattern languages over groups ⋮ Regular patterns, regular languages and context-free languages ⋮ Intrinsic complexity of partial learning ⋮ Weakly unambiguous morphisms ⋮ The complexity of verbal languages over groups ⋮ Bad News on Decision Problems for Patterns ⋮ A note on the complexity of matching patterns with variables ⋮ Discontinuities in pattern inference ⋮ Learning indexed families of recursive languages from positive data: A survey ⋮ Patterns with bounded treewidth ⋮ Learning concepts and their unions from positive data with refinement operators ⋮ Unambiguous erasing morphisms in free monoids ⋮ Automatic learning of subclasses of pattern languages ⋮ The unambiguity of segmented morphisms ⋮ Unambiguous Erasing Morphisms in Free Monoids ⋮ Finitely distinguishable erasing pattern languages ⋮ Commutative Regular Shuffle Closed Languages, Noetherian Property, and Learning Theory ⋮ UNAMBIGUOUS MORPHIC IMAGES OF STRINGS ⋮ Learning Pattern Languages over Groups ⋮ Bad news on decision problems for patterns ⋮ Pattern matching with variables: a multivariate complexity analysis

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
• Avoidable patterns in strings of symbols
• Finding patterns common to a set of strings
• Research in the theory of inductive inference by GDR mathematicians - A survey
• The synthesis of language learners.
• Decision problems for patterns
• Inductive inference of formal languages from positive data
• Ignoring data may be the only way to learn efficiently
• Finite degrees of ambiguity in pattern languages
• Learning Theory
• Pattern languages with and without erasing
• Abelian squares are avoidable on 4 letters
• STACS 2004
• Language identification in the limit

This page was built for publication: A non-learnable class of E-pattern languages