Freydenberger_Reidenbach_TCS_Descriptive_Patterns[1].pdf (265.71 kB)

Existence and nonexistence of descriptive patterns

Download (265.71 kB)
journal contribution
posted on 06.07.2010 by Dominik Freydenberger, Daniel Reidenbach
In the present paper, we study the existence of descriptive patterns, i. e. patterns that cover all words in a given set through morphisms and that are optimal in terms of revealing commonalities of these words. Our main result shows that if patterns may be mapped to words by arbitrary morphisms, then there exist infinite sets of words that do not have a descriptive pattern. This answers a question posed by Jiang et al. (Pattern languages with and without erasing, International Journal of Computer Mathematics 50 (1994)). Since the problem of whether a pattern is descriptive depends on the inclusion relation of so-called pattern languages, our technical considerations lead to a number of deep insights into the inclusion problem for and the topology of the class of terminal-free E-pattern languages.

History

School

  • Science

Department

  • Computer Science

Citation

FREYDENBERGER, D.D. and REIDENBACH, D., 2010. Existence and nonexistence of descriptive patterns. Theoretical Computer Science, 411 (34-36), pp. 3274-3286.

Publisher

© Elsevier

Version

AM (Accepted Manuscript)

Publication date

2010

Notes

This article was published in the journal, Theoretical Computer Science [© Elsevier] and the definitive version is available at: www.elsevier.com/locate/tcs

ISSN

0304-3975

Language

en

Exports

Logo branding

Exports