Well-Structured Pushdown System: Case of Dense Timed Pushdown Automata

• Cai, Xiaojuan

• Ogawa, Mizuhito

抄録

This paper investigates a general framework of a pushdown system with well-quasi-ordered states and stack alphabet to show decidability of reachability, which is an extension of our earlier work (Well-structured Pushdown Systems, CONCUR 2013). As an instance, an alternative proof of the decidability of the reachability for dense-timed pushdown system (in P.A.Abdulla, M.F. Atig, F. Stenman, Dense-Timed Pushdown Automata, IEEE LICS 2012) is presented. Our proof would be more robust for extensions, e.g., regular valuations with time.

12th International Symposium, FLOPS 2014, Kanazawa, Japan, June 4-6, 2014.

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/12784

収録刊行物

• Lecture Notes in Computer Science

  Lecture Notes in Computer Science 8475 336-352, 2014-06

  Springer

キーワード

• Timed Pushdown Automaton
• Reachability
• Decidability
• Well structured pushdown systems

詳細情報

• CRID: 1050282812515168000
• NII論文ID: 120005611454
• ISSN: 03029743
• Web Site: http://hdl.handle.net/10119/12784
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles