Streaming Automatentheorie

• Antragsteller: Professor Dr. Markus Lohrey
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 389127780

Streaming-Algorithmen sind gegenwärtig ein aktives Forschungsgebiet. In 2022 zählten wir 14 Arbeiten zu Streaming-Algorithmen in den internationalen Topkonferenzen zur Theoretischen Informatik (FOCS, ICALP, SODA, und STOC). Typische Probleme, die in diesen Arbeiten behandelt werden, sind die speicherplatzeffiziente Berechnung statistischer Informationen über Datenströme, Streaming-Algorithmen für Graphen und die Verarbeitung von Datenbankabfragen auf Datenströmen. In der ersten Förderperiode des Projekts haben wir uns auf Sliding-Window-Streaming-Algorithmen für formale Sprachen konzentriert. Dies führte zu einer automatentheoretischen Perspektive für Streaming-Algorithmen. Durch die Kombination von automatentheoretischen Werkzeugen mit algorithmischen Methoden haben wir eine Reihe neuer Ergebnisse für Sliding-Window-Streaming-Algorithmen erzielt und die meisten der im ersten Projektantrag gestellten Fragen gelöst. Für die zweite Förderperiode stellen wir uns die folgenden Hauptziele: - Vervollständigung des Bildes zu Sliding-Window-Algorithmen für formale Sprachen: Während der ersten Förderperiode kamen mehrere neue Forschungsfragen auf. Diese betreffen die Zeit- und Platzkomplexität von Sliding-Window-Streaming-Algorithmen für kontextfreie Sprachen und die automatische Konstruktion von speicherplatzoptimalen Sliding-Window-Streaming-Algorithmen. Diese Fragen sollen untersucht werden. - Erweiterung unseres Fokus auf neue Forschungsrichtungen: Einerseits wollen wir auch Streaming-Algorithmen für formale Sprachen im Standard-Streaming-Modell untersuchen, bei denen alte Symbole nicht verfallen, d.h. der gesamte bisher gelesenen Präfix des Datenstroms ist relevant. Die deterministische Platzkomplexität einer Sprache L im Standard-Streaming-Modell steht in einer direkten Beziehung zu der sogenannten Automatizität von L. Motiviert durch diese Korrespondenz planen wir, das neue Konzept der probabilistischen Automatizität einer formalen Sprache zu untersuchen. Eine weitere Richtung, die wir erforschen wollen, ist die Ausweitung unserer Arbeit auf dynamische Membership-Algorithmen für formale Sprachen.

• DFG-Verfahren: Sachbeihilfen