上海交通大学学报

上海交通大学学报（自然版） ›› 2015, Vol. 49 ›› Issue (08): 1084-1089.

• 自动化技术、计算机技术 • 上一篇    下一篇

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

靳阳,蔡小娟,李国强   

  1. (上海交通大学 BASICS实验室,上海 200240)
  • 收稿日期:2014-10-28 出版日期:2015-08-31 发布日期:2015-08-31
  • 基金资助:

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

Expressiveness of WellStructured Pushdown Systems

JIN Yang,CAI Xiaojuan,LI Guoqiang   

  1. (BASICS Laboratory, Shanghai Jiaotong University, Shanghai 200240, China)
  • Received:2014-10-28 Online:2015-08-31 Published:2015-08-31

摘要：

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

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

Abstract:

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.

Key words: well-structured pushdown system, well-quasi-order, vector addition system, reachability problem

中图分类号: