Revisiting Shinohara's algorithm for computing descriptive patterns
From MaRDI portal
Publication:2636407
DOI10.1016/j.tcs.2018.04.035zbMath1408.68085OpenAlexW2377412172WikidataQ129767375 ScholiaQ129767375MaRDI QIDQ2636407
Henning Fernau, Robert Mercaş, Florin Manea, Markus L. Schmid
Publication date: 5 June 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://dspace.lboro.ac.uk/2134/24634
Computational learning theory (68Q32) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (4)
Blocksequences of \(k\)-local words ⋮ Matching patterns with variables under edit distance ⋮ Detecting One-Variable Patterns ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Inferring descriptive generalisations of formal languages
- Patterns with bounded treewidth
- Three \(\sum^ P_ 2\)-complete problems in computational learning theory
- Polynomial-time inference of arbitrary pattern languages
- Existence and nonexistence of descriptive patterns
- Bad news on decision problems for patterns
- A note on the two-variable pattern-finding problem
- Finding patterns common to a set of strings
- Decision problems for patterns
- Learnability and the Vapnik-Chervonenkis dimension
- Difficulties in Forcing Fairness of Polynomial Time Inductive Inference
- A theory of the learnable
- Inductive inference of formal languages from positive data
- Ignoring data may be the only way to learn efficiently
- Distinguishing Pattern Languages with Membership Examples
- Inductive inference of unbounded unions of pattern languages from positive data
- Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries
This page was built for publication: Revisiting Shinohara's algorithm for computing descriptive patterns
