Streaming Automata Theory

流自动机理论

基本信息

项目摘要

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

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Professor Dr. Markus Lohrey其他文献

Professor Dr. Markus Lohrey的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Professor Dr. Markus Lohrey', 18)}}的其他基金

Algorithmic Problems in Group Theory
群论中的算法问题
  • 批准号:
    288360912
  • 财政年份:
    2016
  • 资助金额:
    --
  • 项目类别:
    Research Grants
Data Compression for Active Diagnosis
用于主动诊断的数据压缩
  • 批准号:
    275601549
  • 财政年份:
    2015
  • 资助金额:
    --
  • 项目类别:
    Research Grants
Quantitative Aspects of Grammar-Based Compression
基于语法的压缩的定量方面
  • 批准号:
    261105198
  • 财政年份:
    2014
  • 资助金额:
    --
  • 项目类别:
    Research Grants
Algorithmen für komprimierte Daten (ALKODA)
压缩数据算法 (ALKODA)
  • 批准号:
    76592132
  • 财政年份:
    2008
  • 资助金额:
    --
  • 项目类别:
    Research Grants
Graphen mit entscheidbaren Logiken (GELO)
具有可判定逻辑的图 (GELO)
  • 批准号:
    31332468
  • 财政年份:
    2006
  • 资助金额:
    --
  • 项目类别:
    Research Grants
Graphen mit entscheidbaren Logiken
具有可判定逻辑的图
  • 批准号:
    5430209
  • 财政年份:
    2004
  • 资助金额:
    --
  • 项目类别:
    Priority Programmes

相似海外基金

Application of automata and transducers to computational semigroup theory
自动机和传感器在计算半群论中的应用
  • 批准号:
    2590267
  • 财政年份:
    2021
  • 资助金额:
    --
  • 项目类别:
    Studentship
Chemical Reaction Computation based on Reaction Automata Theory
基于反应自动机理论的化学反应计算
  • 批准号:
    17K00021
  • 财政年份:
    2017
  • 资助金额:
    --
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Construction of a unified theory for cellular automata using algebraic structure of lattice
利用格子代数结构构建元胞自动机统一理论
  • 批准号:
    26600156
  • 财政年份:
    2014
  • 资助金额:
    --
  • 项目类别:
    Grant-in-Aid for Challenging Exploratory Research
Theory and applications of cellular automata and iterated systems
元胞自动机和迭代系统的理论与应用
  • 批准号:
    24817-2009
  • 财政年份:
    2013
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
Theory and applications of cellular automata and iterated systems
元胞自动机和迭代系统的理论与应用
  • 批准号:
    24817-2009
  • 财政年份:
    2012
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
Automata in semigroup theory, group theory and analysis
半群论、群论和分析中的自动机
  • 批准号:
    262403-2007
  • 财政年份:
    2011
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
Theory and applications of automata and codes
自动机和代码的理论与应用
  • 批准号:
    217247-2007
  • 财政年份:
    2011
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
Theory and applications of cellular automata and iterated systems
元胞自动机和迭代系统的理论与应用
  • 批准号:
    24817-2009
  • 财政年份:
    2011
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
Automata in semigroup theory, group theory and analysis
半群论、群论和分析中的自动机
  • 批准号:
    262403-2007
  • 财政年份:
    2010
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
Theory and applications of cellular automata and iterated systems
元胞自动机和迭代系统的理论与应用
  • 批准号:
    24817-2009
  • 财政年份:
    2010
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了