descriptive_patterns_TCS_Learning_Complexity.pdf (422.17 kB)
0/0

Revisiting Shinohara's algorithm for computing descriptive patterns

Download (422.17 kB)
journal contribution
posted on 05.04.2017 by Henning Fernau, Florin Manea, Robert Mercas, Markus L. Schmid
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.

Funding

The work of Florin Manea was supported by by DFG grant number 596676. The work of Robert Mercas was supported by the P.R.I.M.E. programme of DAAD with funds provided by the Federal Ministry of Education and Research (BMBF) and the European Unions Seventh Framework Programme for research, technological development and demonstration (grant agreement no. 605728).

History

School

  • Science

Department

  • Computer Science

Published in

Theoretical Computer Science

Citation

FERNAU, H. ... et al, 2017. Revisiting Shinohara's algorithm for computing descriptive patterns. Theoretical Computer Science, 733, pp.44-54.

Publisher

© Elsevier

Version

AM (Accepted Manuscript)

Publisher statement

This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/

Acceptance date

06/10/2016

Publication date

2018-05-25

Notes

This paper was accepted for publication in the journal Theoretical Computer Science and the definitive published version is available at https://doi.org/10.1016/j.tcs.2018.04.035

ISSN

0304-3975

Language

en

Exports