*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion 16
Dienstag, 19.09.2000, 14.00–14.20 Uhr, WIL C 307

Aperiodische und sternfreie formale Potenzreihen

Manfred Droste, TU Dresden

Formale Potenzreihen über Wörtern und mit Einträgen in einem Semiring K stellen das Verhalten von Automaten mit Kostenfunktionen für die Zustandsübergänge dar. Wir definieren aperiodische und sternfreie formale Potenzreihen in teilweise kommutierenden Variablen. Wir zeigen: Ist der Semiring K idempotent und kommutativ, so ist das Produkt von zwei aperiodischen formalen Potenzreihen wieder aperiodisch. Haben darüberhinaus die Matrizenmonoide über K eine Burnside-Eigenschaft (dies ist erfüllt für den tropischen Semiring), so stimmen aperiodische und sternfreie formale Potenzreihen überein. Dies verallgemeinert ein klassisches Resultat von Schützenberger (1961) über aperiodische Sprachen und ein Resultat von Guaiana, Restivo, Salemi (1992) über aperiodische Spur-Sprachen. (Gemeinsame Arbeit mit P. Gastin, Paris.)