The Complexity of Coverability in ν-Petri Nets

机译：ν-Petri网覆盖性的复杂性

获取原文

页面导航

摘要
著录项
相似文献
相关主题

摘要

We show that the coverability problem in ν-Petri nets is complete for `double Ackermann' time, thus closing an open complexity gap between an Ackermann lower bound and a hyper-Ackermann upper bound. The coverability problem captures the verification of safety properties in this nominal extension of Petri nets with name management and fresh name creation. Our completeness result establishes ν-Petri nets as a model of intermediate power among the formalisms of nets enriched with data, and relies on new algorithmic insights brought by the use of well-quasi-order ideals.

机译：我们证明了在ν-Petri网络中的可覆盖性问题在“双重Ackermann”时间内是完整的，因此弥合了Ackermann下限和hyper-Ackermann上限之间的开放性复杂性差距。可覆盖性问题通过名称管理和新名称创建来捕获Petri网这种名义扩展中的安全属性验证。我们的完整性结果将ν-Petri网络建立为充斥数据的网络形式主义中的中间力量模型，并依赖于使用准序理想带来的新算法洞察力。

著录项

来源
《Annual ACM/IEEE Symposium on Logic in Computer Science》|2016年|1-10|共10页
会议地点
作者
Ranko Lazić; Sylvain Schmitz;
展开▼
作者单位

展开▼
会议组织
原文格式 PDF
正文语种
中图分类
关键词
Petri nets; Complexity theory; Upper bound; Reactive power; Semantics; Syntactics; Safety;

机译：Petri网;复杂性理论;上限;无功;语义;句法;安全;

相似文献

外文文献
中文文献
专利

1. Petri nets Analysis: Complexity and Finite Coverability Graph in Modular Design [J] . D. Crestani, A. Jean-Marie, C. Coves Studies in Informatics and Control . 2005,第1期

机译：Petri网分析：模块化设计中的复杂性和有限覆盖图
2. Small Vertex Cover makes Petri Net Coverability and Boundedness Easier [J] . M. Praveen Algorithmica . 2013,第4期

机译：较小的顶点覆盖范围使Petri网的覆盖范围和边界更容易
3. Assigning the cover of Petri nets with subnets of the automatic type [J] . Robert DYLEWSKI Przeglad Elektrotechniczny . 2013,第11期

机译：用自动类型的子网分配陪替氏网络的封面
4. Parameterized Complexity and Approximability of Coverability Problems in Weighted Petri Nets [C] . Dimitri Watel, Marc-Antoine Weisser, Dominique Barth International conference on application and theory of petri nets and concurrency . 2017

机译：加权Petri网的可覆盖性问题的参数化复杂度和逼近性
5. ANALYSIS OF DISTRIBUTED SYSTEM SOFTWARE DESIGN BASED ON STRUCTURED PETRI NET MODEL (PERFORMANCE, PETRI NET) [D] . CHOU, CHING-ROUNG 1986

机译：基于结构化PETRI NET模型（性能，PETRI NET）的分布式系统软件设计分析
6. Single Cell Mass Cytometry of Non-Small Cell Lung Cancer Cells Reveals Complexity of In Vivo and Three-Dimensional Models over the Petri-Dish [O] . Róbert Alföldi, József Á. Balog, Nóra Faragó, 2019

机译：非小细胞肺癌细胞的单细胞大规模细胞计数揭示了培养皿上的体内和三维模型的复杂性。
7. Parameterized Complexity and Approximability of Coverability Problems in Weighted Petri Nets [O] . Dimitri Watel, Marc-Antoine Weisser, Dominique Barth 2017

机译：加权Petri网中覆盖性问题的参数化复杂性和近似性

The Complexity of Coverability in ν-Petri Nets

摘要

著录项

相似文献

相关主题

期刊订阅