Streaming Automata Theory

• Applicant: Professor Dr. Markus Lohrey
• Subject Area: Theoretical Computer Science
• Term: since 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 389127780

Streaming algorithms are currently a very active research area. In 2022, we counted 14 papers on streaming in the top international conferences in theoretical computer science (FOCS, ICALP, SODA, and STOC). Typical problems addressed in these papers are the computation of statistical information over data streams in small space, graph algorithms for streamed graphs, and query processing. In the first funding period of the project we have focused on sliding window streaming algorithms for formal languages. This led to a more automata theoretic perspective on streaming algorithms. By combining automata-theoretic tools with algorithmic methods, we have obtained new results for sliding window algorithms and have solved most of the questions posed in the first project proposal. The main objectives for the second funding period are the following: - Completing the picture on sliding window algorithms for formal languages: Several new research questions came up during the first funding period. These concern the time and space complexity of sliding window algorithms for context-free languages and the automatic construction of space optimal sliding window algorithms. - Extension our research focus to new directions: On the one hand, we also want to study streaming algorithms for formal languages in the standard streaming model, where old symbols do not expire, i.e., the sliding window consists of the whole prefix read so far. The deterministic space complexity of a language L in the standard streaming model is one-to-one related to the so-called automaticity of L. Motivated by this correspondence, we plan to investigate the new concept of probabilistic automaticity of a language. Another research direction that we plan to explore is the extension of our work to dynamic membership algorithms for formal languages.

• DFG Programme: Research Grants