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

来源：软件学报杂志2018年第10期北京时间：

作者：李春淼,蔡小娟,李国强

单位：李春淼，上海交通大学 软件学院, 上海 20024011,蔡小娟，上海交通大学 软件学院, 上海 20024002,李国强，上海交通大学 软件学院, 上海 20024003

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

关键词：良结构下推系统;可覆盖性;下界;重置0;Hyper-Ackermann难

基金资助：国家自然科学基金（61472238，61672340，61872232）