Structural liveness of Petri nets is ExpSpace-hard and decidable

Abstract:
Place/transition Petri nets are a standard model for a class of distributed systems whose reachability spaces might be infinite. One of well-studied topics is verification of safety and liveness properties in this model; despite an extensive research effort, some basic problems remain open, which is exemplified by the complexity status of the reachability problem that is still not fully clarified. The liveness problems are known to be closely related to the reachability problem, and various structural properties of nets that are related to liveness have been studied. Somewhat surprisingly, the decidability status of the problem of determining whether a net is structurally live, i.e. whether there is an initial marking for which it is live, remained open for some time; e.g. Best and Esparza (Inf Process Lett 116(6):423–427, 2016. https://doi.org/10.1016/j.ipl.2016.01.011) emphasize this open question. Here we show that the structural liveness problem for Petri nets is ExpSpace-hard and decidable. In particular, given a net N and a semilinear set S, it is decidable whether there is an initial marking of N for which the reachability set is included in S; this is based on results by Leroux (28th annual ACM/IEEE symposium on logic in computer science, LICS 2013, New Orleans, LA, USA, June 25–28, 2013, IEEE Computer Society, pp 23–32, 2013. https://doi.org/10.1109/LICS.2013.7).
Author Listing: Petr Jancar;David Purser
Volume: 56
Pages: 537-552
DOI: 10.1007/s00236-019-00338-6
Language: English
Journal: Acta Informatica

ACTA INFORMATICA

ACTA INFORM

影响因子:0.4 是否综述期刊:否 是否OA:否 是否预警:不在预警名单内 发行时间:1971 ISSN:0001-5903 发刊频率:Monthly 收录数据库:SCIE/Scopus收录 出版国家/地区:GERMANY 出版社:Springer Berlin Heidelberg

期刊介绍

Acta Informatica provides international dissemination of articles on formal methods for the design and analysis of programs, computing systems and information structures, as well as related fields of Theoretical Computer Science such as Automata Theory, Logic in Computer Science, and Algorithmics.Topics of interest include:• semantics of programming languages• models and modeling languages for concurrent, distributed, reactive and mobile systems• models and modeling languages for timed, hybrid and probabilistic systems• specification, program analysis and verification• model checking and theorem proving• modal, temporal, first- and higher-order logics, and their variants• constraint logic, SAT/SMT-solving techniques• theoretical aspects of databases, semi-structured data and finite model theory• theoretical aspects of artificial intelligence, knowledge representation, description logic• automata theory, formal languages, term and graph rewriting• game-based models, synthesis• type theory, typed calculi• algebraic, coalgebraic and categorical methods• formal aspects of performance, dependability and reliability analysis• foundations of information and network security• parallel, distributed and randomized algorithms• design and analysis of algorithms• foundations of network and communication protocols.

Acta Informatica提供关于程序、计算系统和信息结构的设计和分析的形式化方法的文章的国际传播,以及理论计算机科学的相关领域,如自动机理论、计算机科学中的逻辑和算法。感兴趣的主题包括:·编程语言的语义·并发、分布式、反应式和移动的系统的模型和建模语言·定时、混合和概率系统的模型和建模语言·规范、程序分析和验证·模型检查和定理证明·模态、时序、一阶和高阶逻辑及其变体·约束逻辑、SAT/SMT求解技术·数据库的理论方面、半结构化数据和有限模型理论·人工智能的理论方面、知识表示、描述逻辑·自动机理论、形式语言、术语和图形重写·基于博弈的模型、综合·类型论、类型演算·代数、共代数和范畴方法·性能、可靠性和可靠性分析的形式方面·信息和网络安全的

年发文量 14
国人发稿量 3
国人发文占比 21.43%
自引率 0.0%
平均录取率 容易
平均审稿周期 >12周,或约稿
版面费 US$2780
偏重研究方向 工程技术-计算机:信息系统
期刊官网 https://www.springer.com/236/?utm_medium=display&utm_source=letpub&utm_content=text_link&utm_term=null&utm_campaign=MPSR_00236_AWA1_CN_CNPL_letpb_mp
投稿链接 https://submission.nature.com/new-submission/236/3

质量指标占比

研究类文章占比 OA被引用占比 撤稿占比 出版后修正文章占比
92.31% 45.00% 0.00% 3.13%

相关指数

{{ relationActiveLabel }}
{{ item.label }}

期刊预警不是论文评价,更不是否定预警期刊发表的每项成果。《国际期刊预警名单(试行)》旨在提醒科研人员审慎选择成果发表平台、提示出版机构强化期刊质量管理。

预警期刊的识别采用定性与定量相结合的方法。通过专家咨询确立分析维度及评价指标,而后基于指标客观数据产生具体名单。

具体而言,就是通过综合评判期刊载文量、作者国际化程度、拒稿率、论文处理费(APC)、期刊超越指数、自引率、撤稿信息等,找出那些具备风险特征、具有潜在质量问题的学术期刊。最后,依据各刊数据差异,将预警级别分为高、中、低三档,风险指数依次减弱。

《国际期刊预警名单(试行)》确定原则是客观、审慎、开放。期刊分区表团队期待与科研界、学术出版机构一起,夯实科学精神,打造气正风清的学术诚信环境!真诚欢迎各界就预警名单的分析维度、使用方案、值得关切的期刊等提出建议!

预警情况 查看说明

时间 预警情况
2024年02月发布的2024版 不在预警名单中
2023年01月发布的2023版 不在预警名单中
2021年12月发布的2021版 不在预警名单中
2020年12月发布的2020版 不在预警名单中

JCR分区 WOS分区等级:Q4区

版本 按学科 分区
WOS期刊SCI分区
WOS期刊SCI分区是指SCI官方(Web of Science)为每个学科内的期刊按照IF数值排 序,将期刊按照四等分的方法划分的Q1-Q4等级,Q1代表质量最高,即常说的1区期刊。
(2021-2022年最新版)
COMPUTER SCIENCE, INFORMATION SYSTEMS Q4

关于2019年中科院分区升级版(试行)

分区表升级版(试行)旨在解决期刊学科体系划分与学科发展以及融合趋势的不相容问题。由于学科交叉在当代科研活动的趋势愈发显著,学科体系构建容易引发争议。为了打破学科体系给期刊评价带来的桎梏,“升级版方案”首先构建了论文层级的主题体系,然后分别计算每篇论文在所属主题的影响力,最后汇总各期刊每篇论文分值,得到“期刊超越指数”,作为分区依据。

分区表升级版(试行)的优势:一是论文层级的主题体系既能体现学科交叉特点,又可以精准揭示期刊载文的多学科性;二是采用“期刊超越指数”替代影响因子指标,解决了影响因子数学性质缺陷对评价结果的干扰。整体而言,分区表升级版(试行)突破了期刊评价中学科体系构建、评价指标选择等瓶颈问题,能够更为全面地揭示学术期刊的影响力,为科研评价“去四唯”提供解决思路。相关研究成果经过国际同行的认可,已经发表在科学计量学领域国际重要期刊。

《2019年中国科学院文献情报中心期刊分区表升级版(试行)》首次将社会科学引文数据库(SSCI)期刊纳入到分区评估中。升级版分区表(试行)设置了包括自然科学和社会科学在内的18个大类学科。基础版和升级版(试行)将过渡共存三年时间,推测在此期间各大高校和科研院所仍可能会以基础版为考核参考标准。 提示:中科院分区官方微信公众号“fenqubiao”仅提供基础版数据查询,暂无升级版数据,请注意区分。

中科院分区 查看说明

版本 大类学科 小类学科 Top期刊 综述期刊
计算机科学
4区
COMPUTER SCIENCE, INFORMATION SYSTEMS
计算机:信息系统
4区
2021年12月
基础版
工程技术
4区
COMPUTER SCIENCE, INFORMATION SYSTEMS
计算机:信息系统
4区
2021年12月
升级版
计算机科学
4区
COMPUTER SCIENCE, INFORMATION SYSTEMS
计算机:信息系统
4区
2020年12月
旧的升级版
计算机科学
3区
COMPUTER SCIENCE, INFORMATION SYSTEMS
计算机:信息系统
3区
2022年12月
最新升级版
计算机科学
4区
COMPUTER SCIENCE, INFORMATION SYSTEMS
计算机:信息系统
4区