Revisiting Shinohara's algorithm for computing descriptive patterns
| Autor: | Henning Fernau, Markus L. Schmid, Florin Manea, Robert Mercaş |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Polynomial
General Computer Science Computer science Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) 0102 computer and information sciences 02 engineering and technology Inductive reasoning 01 natural sciences Theoretical Computer Science Pattern language (formal languages) Set (abstract data type) 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Constant (mathematics) Algorithm Finite set Computer Science::Formal Languages and Automata Theory Word (group theory) |
| Zdroj: | Theoretical Computer Science. 733:44-54 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2018.04.035 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect