15. ÖMG-Kongress
Jahrestagung der Deutschen Mathematikervereinigung

16. bis 22. September 2001 in Wien

Sektion 3 - Diskrete Mathematik, Algorithmen
Donnerstag, 20. September 2001, 15.00, Hörsaal 23

 

Über das Wachstum kontextfreier Sprachen

Wolfgang Woess, TU Graz (Koautor: Tullio Ceccherini-Silberstein (Rom))

Es wird gezeigt, dass jede kontextfreie Sprache $L$, die von einer nichtlinearen, eindeutigen, ergodischen Grammatik erzeugt wird, wachstumssensitiv ist. Das bedeutet folgendes: sei $F$ eine endliche Menge von Worten, die als Teilworte von Elementen von $L$ auftreten, und sei $L^F$ die Menge aller Elemente von $L$, die kein Wort aus $F$ als Teilwort enthalten. Dann ist das Wachstum von $L^F$ strikt (exponentiell) kleiner als jenes von $L$. (Eine kontextfreie Grammatik heiß t ergodisch, wenn ihr Abhängigkeits-Digraph stark zusammenhängend ist.)

E-Mail:

woess@weyl.math.tu-graz.ac.at

Zeitplan der Sektion   Tagesübersicht   Liste der Vortragenden