Discontinuities in pattern inference
From MaRDI portal
Publication:924176
DOI10.1016/j.tcs.2008.02.029zbMath1145.68027OpenAlexW1970263043MaRDI QIDQ924176
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
Computational learning theory (68Q32) Combinatorics on words (68R15) Formal languages and automata (68Q45)
Related Items
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
