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

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

Expressiveness of Well-Structured Pushdown Systems

Abstract： A well-structured pushdown system(WSPDS) is a pushdown system equipped with well-quasi-order states and a well-quasi-order stack alphabet. It is shown that several extensions of vector addition systems can be reduced to a WSPDS. By applying post-order calculation of its derivation tree, the branching vector addition system can be encoded to some WSPDS. The recursive vector addtion system is a special class of WSPDS if a stack is explicitly introduced to its transitions. The vector addtion system with one zero-test can be encoded to some WSPDS where the depth of the stack represents the dimension for zero test. These results exhibit the powerful expressivenss of WSPDS.