2134/24634 Henning Fernau Henning Fernau Florin Manea Florin Manea Robert Mercas Robert Mercas Markus L. Schmid Markus L. Schmid Revisiting Shinohara's algorithm for computing descriptive patterns Loughborough University 2017 Pattern languages Inductive inference Descriptive patterns N P-hard problems 2010 MSC: 68Q25, 68Q17, 68Q32 Information and Computing Sciences not elsewhere classified 2017-04-05 09:15:37 Journal contribution https://repository.lboro.ac.uk/articles/journal_contribution/Revisiting_Shinohara_s_algorithm_for_computing_descriptive_patterns/9401570 A pattern α is a word consisting of constants and variables and it describes the pattern language L(α) of all words that can be obtained by uniformly replacing the variables with constant words. In 1982, Shinohara presents an algorithm that computes a pattern that is descriptive for a finite set S of words, i.e., its pattern language contains S in the closest possible way among all pattern languages. We generalise Shinohara’s algorithm to subclasses of patterns and characterise those subclasses for which it is applicable. Furthermore, within this set of pattern classes, we characterise those for which Shinohara’s algorithm has a polynomial running time (under the assumption P 6= N P). Moreover, we also investigate the complexity of the consistency problem of patterns, i.e., finding a pattern that separates two given finite sets of words.