首页    期刊浏览 2024年12月03日 星期二
登录注册

文章基本信息

  • 标题:Automata Theory on Sliding Windows
  • 作者:Moses Ganardi ; Danny Hucke ; Daniel K{\"o}nig
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:96
  • 页码:31:1-31:14
  • DOI:10.4230/LIPIcs.STACS.2018.31
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:In a recent paper we analyzed the space complexity of streaming algorithms whose goal is to decide membership of a sliding window to a fixed language. For the class of regular languages we proved a space trichotomy theorem: for every regular language the optimal space bound is either constant, logarithmic or linear. In this paper we continue this line of research: We present natural characterizations for the constant and logarithmic space classes and establish tight relationships to the concept of language growth. We also analyze the space complexity with respect to automata size and prove almost matching lower and upper bounds. Finally, we consider the decision problem whether a language given by a DFA/NFA admits a sliding window algorithm using logarithmic/constant space.
  • 关键词:regular languages; sliding window algorithms
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有