Freydenberger_Reidenbach_DLT09_Final_Version_Descriptive_Patterns.pdf (209.6 kB)

Existence and nonexistence of descriptive patterns

Download (209.6 kB)
conference contribution
posted on 10.07.2009, 13:26 by Dominik FreydenbergerDominik Freydenberger, Daniel ReidenbachDaniel 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 onto 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, Kinber, Salomaa, Salomaa and Yu (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 Epattern languages.

History

School

  • Science

Department

  • Computer Science

Citation

FREYDENBERGER, D.D. and REIDENBACH, D., 2009. Existence and nonexistence of descriptive patterns. IN: Developments in Language Theory, 13th International Conference, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009, Proceedings. Springer Berlin / Heidelberg, pp. 228-239

Publisher

© Springer Berlin / Heidelberg

Version

AM (Accepted Manuscript)

Publication date

2009

Notes

This paper was published in the series Lecture Notes in Computer Science [© Springer Berlin / Heidelberg] and the original publication is available at www.springerlink.com

ISBN

9783642027369

ISSN

0302-9743;1611-3349

Book series

Lecture Notes in Computer Science;5583

Language

en

Usage metrics

Keywords

Exports