首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:Two-Way Parikh Automata
  • 本地全文:下载
  • 作者:Emmanuel Filiot ; Shibashis Guha ; Nicolas Mazzocchi
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2019
  • 卷号:150
  • 页码:1-14
  • DOI:10.4230/LIPIcs.FSTTCS.2019.40
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:Parikh automata extend automata with counters whose values can only be tested at the end of the computation, with respect to membership into a semi-linear set. Parikh automata have found several applications, for instance in transducer theory, as they enjoy a decidable emptiness problem. In this paper, we study two-way Parikh automata. We show that emptiness becomes undecidable in the non-deterministic case. However, it is PSpace-C when the number of visits to any input position is bounded and the semi-linear set is given as an existential Presburger formula. We also give tight complexity bounds for the inclusion, equivalence and universality problems. Finally, we characterise precisely the complexity of those problems when the semi-linear constraint is given by an arbitrary Presburger formula.
  • 关键词:Parikh automata; two-way automata; Presburger arithmetic
国家哲学社会科学文献中心版权所有