Freydenberger_Reidenbach_DLT09_Final_Version_Descriptive_Patterns.pdf (209.6 kB)
Download fileExistence and nonexistence of descriptive patterns
conference contribution
posted on 2009-07-10, 13:26 authored by Dominik FreydenbergerDominik Freydenberger, Daniel ReidenbachIn 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