良结构下推系统的表达能力

摘要

良结构下推系统是将状态集和栈字符集都扩展为良拟序的下推系统.研究向量加法系统及其扩展系统与良结构下推系统的关系,证明了多个模型可归约到良结构下推系统.通过树的后序遍历构造了分支向量加法系统到良结构下推系统的编码;通过显式引入栈证明递归向量加法系统是良结构下推系统的一种特例;创新地使用栈深表示向量的一维,来构造一位零测试向量加法系统到良结构下推系统的编码.通过这些编码证明了良结构下推系统的表达能力不低于这些向量加法扩展系统,进一步说明了良结构下推系统的一般性.