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

摘要：

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

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

所属期刊栏目：29

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金61472238,61672340,61872232

在线出版日期：2018-11-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：3009-3020