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

文章基本信息

  • 标题:Parametrized Universality Problems for One-Counter Nets
  • 本地全文:下载
  • 作者:Shaull Almagor ; Udi Boker ; Piotr Hofman
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2020
  • 卷号:171
  • 页码:47:1-47:16
  • DOI:10.4230/LIPIcs.CONCUR.2020.47
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We study the language universality problem for One-Counter Nets, also known as 1-dimensional Vector Addition Systems with States (1-VASS), parameterized either with an initial counter value, or with an upper bound on the allowed counter value during runs. The language accepted by an OCN (defined by reaching a final control state) is monotone in both parameters. This yields two natural questions: 1) does there exist an initial counter value that makes the language universal? 2) does there exist a sufficiently high ceiling so that the bounded language is universal? Although the ordinary universality problem is decidable (and Ackermann-complete) and these parameterized variants seem to reduce to checking basic structural properties of the underlying automaton, we show that in fact both problems are undecidable. We also look into the complexities of the problems for several decidable subclasses, namely for unambiguous, and deterministic systems, and for those over a single-letter alphabet.
  • 关键词:Counter net; VASS; Unambiguous Automata; Universality
国家哲学社会科学文献中心版权所有