良结构下推系统的可覆盖性问题的下界

• 作者: 李国强 李春淼 蔡小娟
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 良结构下推系统 可覆盖性 下界 重置0 Hyper-Ackermann难
• 年，卷（期）: 2018,（10）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 3009-3020
• 页数: 12页
• 分类号: TP301
• 字数: 9150字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005321

摘要

良结构下推系统是下推系统和良结构迁移系统的结合,该系统允许状态和栈字符是向量的形式,因而它们是无限的.状态迁移的同时允许栈进行入栈出栈的操作.它“非常接近不可判定的边缘”.利用重置0操作,提出了一种模型可覆盖性问题复杂度下界的一般性证明方法,并且证明了状态是三维向量的子集和一般性的良结构下推系统的可覆盖性问题分别是Tower难和Hyper-Ackermann难的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李国强	上海交通大学软件学院	13	44	4.0	6.0
2	蔡小娟	上海交通大学软件学院	3	15	1.0	3.0
3	李春淼	上海交通大学软件学院	1	0	0.0	0.0