Discontinuities in pattern inference

DOI10.1016/j.tcs.2008.02.029zbMath1145.68027OpenAlexW1970263043MaRDI QIDQ924176

Daniel Reidenbach

Publication date: 28 May 2008

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

Full work available at URL: https://figshare.com/articles/Discontinuities_in_pattern_inference/9401606

zbMATH Keywords

ambiguityinductive inferencemorphismscombinatorics on wordspattern languagestelltales

Mathematics Subject Classification ID

Computational learning theory (68Q32) Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items (24)

Ambiguity of Morphisms in a Free Group ⋮ A parameterized study of maximum generalized pattern matching problems ⋮ Closure properties of pattern languages ⋮ The Billaud conjecture for \(|\varSigma| = 4\), and beyond ⋮ Inferring descriptive generalisations of formal languages ⋮ Regular and context-free pattern languages over small alphabets ⋮ Weakly unambiguous morphisms ⋮ Bad News on Decision Problems for Patterns ⋮ A note on the complexity of matching patterns with variables ⋮ Learning indexed families of recursive languages from positive data: A survey ⋮ Patterns with bounded treewidth ⋮ Unambiguous erasing morphisms in free monoids ⋮ The unambiguity of segmented morphisms ⋮ Restricted ambiguity of erasing morphisms ⋮ Unambiguous Erasing Morphisms in Free Monoids ⋮ Unnamed Item ⋮ Finitely distinguishable erasing pattern languages ⋮ On Billaud words and their companions ⋮ On Billaud words and their companions ⋮ Morphically primitive words ⋮ Unnamed Item ⋮ Bad news on decision problems for patterns ⋮ Pattern matching with variables: a multivariate complexity analysis ⋮ Unambiguous injective morphisms in free groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding a homomorphism between two words is NP-complete
• Polynomial-time inference of arbitrary pattern languages
• A non-learnable class of E-pattern languages
• Finding patterns common to a set of strings
• On the equivalence problem for E-pattern languages
• An average-case optimal one-variable pattern language learner
• The synthesis of language learners.
• Decision problems for patterns
• Strongly prime PCP words
• Formal language identification: query learning vs. gold-style learning
• Relations between Gold-style learning and query learning
• Inductive inference of formal languages from positive data
• Fixed languages and the adult languages of ol schemest^†
• 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
• STACS 2004
• UNAMBIGUOUS MORPHIC IMAGES OF STRINGS
• Language identification in the limit
• Developments in Language Theory
• Stochastic finite learning of the pattern languages

This page was built for publication: Discontinuities in pattern inference