Inclusion of Pattern Languages and Related Problems

Abstract

Patternsprachen sind ein einfacher und eleganter Mechanismus zur Beschreibung von Sprachen, deren Wörter über Wiederholungen definiert sind. Trotz dieser Einfachheit sind viele der kanonischen Fragestellungen für Patternsprachen überraschend schwer zu lösen. Die vorliegende Arbeit befasst sich mit verschiedenen Aspekten des Inklusionsproblems für Patternsprachen. Neben Beweisen zur Unentscheidbarkeit dieses Problems, selbst für verschiedene stark eingeschränkte Unterklassen, werden die Resultate auf regex, eine in modernen Programmiersprachen weit verbreitete Erweiterung der regulären Ausdrücke übertragen. Ein weiterer Schwerpunkt der Untersuchungen sind die Existenz und Berechnung deskriptiver Pattern, welche inklusionsminimale Verallgemeinerungen beliebiger Sprachen durch Patternsprachen darstellen.