Streaming Automata Theory

流媒体算法是当前一个非常活跃的研究领域。2022年，我们在理论计算机科学的顶级国际会议（FOCS，ICALP，SODA和STOC）中统计了14篇关于流媒体的论文。在这些文件中解决的典型问题是在小空间的数据流，流图的图形算法，和查询处理的统计信息的计算。在项目的第一个资助期，我们专注于正式语言的滑动窗口流算法。这导致了对流算法的自动机理论观点。通过将自动机理论工具与算法方法相结合，我们获得了滑动窗口算法的新结果，并解决了第一个项目提案中提出的大部分问题。第二个资助期的主要目标如下：-完成形式语言的滑动窗口算法：在第一个资助期出现了几个新的研究问题。这些问题涉及上下文无关语言滑动窗口算法的时间和空间复杂度以及空间最优滑动窗口算法的自动构造。- 将我们的研究重点扩展到新的方向：一方面，我们还想研究标准流模型中形式语言的流算法，其中旧符号不会过期，即，滑动窗口由到目前为止读取的整个前缀组成。在标准流模型中，语言L的确定性空间复杂度与L的所谓自动性一一相关。受这种对应关系的启发，我们计划研究语言的概率自动性的新概念。我们计划探索的另一个研究方向是将我们的工作扩展到形式语言的动态成员算法。

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.