Logische Klassifizierung regulärer Sprachen

Die folgenden Begriffe haben genau die gleiche Ausdruckskraft bei der Beschreibung von Sprachen (von Wörtern und Bäumen):

Durch Einschränkung erhalten wir Teiklassen. Eine interessante Klasse von Wortsprachen sind diejenigen, die beschrieben werden durch

Diese Klasse wird von der Straubing-Hierarchie ausgeschöpft.

Der Vortrag präsentiert dazugehörige Definitionen, Sätze und Beweisideen und erwähnt offenen Probleme, insbesondere beim Übertragen der Begriffe auf Baumsprachen.

Literatur:


this page is best viewed with any browser


http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de