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

Expressiveness of Well-Structured Pushdown Systems

作　　者：靳阳[1] 蔡小娟[1] 李国强[1] 

机构地区：[1]上海交通大学BASICS实验室,上海200240

出　　处：《上海交通大学学报》2015年第8期1084-1089,共6页Journal of Shanghai Jiaotong University

基　　金：国家自然科学基金项目(61472238;61100053)资助

摘　　要：良结构下推系统是将状态集和栈字符集都扩展为良拟序的下推系统.研究向量加法系统及其扩展系统与良结构下推系统的关系,证明了多个模型可归约到良结构下推系统.通过树的后序遍历构造了分支向量加法系统到良结构下推系统的编码;通过显式引入栈证明递归向量加法系统是良结构下推系统的一种特例;创新地使用栈深表示向量的一维,来构造一位零测试向量加法系统到良结构下推系统的编码.通过这些编码证明了良结构下推系统的表达能力不低于这些向量加法扩展系统,进一步说明了良结构下推系统的一般性.A well-structured pushdown system（WSPDS）is a pushdown system equipped with well-quasiorder 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 zerotest.These results exhibit the powerful expressivenss of WSPDS.

关 键 词：良结构下推系统 良拟序 向量加法系统 可达性问题 

分 类 号：TP301.2[自动化与计算机技术—计算机系统结构]