Well-Structured Pushdown Systems, Part 1: Decidable Classes for Coverability

Material type: 文書・図像類

Author: Cai, Xiaojuanほか

Publisher: 北陸先端科学技術大学院大学情報科学研究科

Publication date: 2013-01-08

Material Format: Digital

Capacity, size, etc.: -

NDC: -

View All

Notes on use

Note (General)：: Pushdown systems (PDSs) nicely model single-thread recursive programs, and well-structured transition systems (WSTS), such as vector addition systems,...

Search by Bookstore

Holdings of Libraries in Japan

This page shows libraries in Japan other than the National Diet Library that hold the material.

List of Cooperating Institutions and Databases

Please contact your local library for information on how to use materials or whether it is possible to request materials from the holding libraries.

other

JAIST Repository
Digital
You can check the holdings of institutions and databases with which Institutional Repositories DataBase(IRDB)(Institutional Repository) is linked at the site of Institutional Repositories DataBase(IRDB)(Institutional Repository).
JAIST Repository

Search by Bookstore

Bibliographic Record

You can check the details of this material, its authority (keywords that refer to materials on the same subject, author's name, etc.), etc.

Digital

Material Type: 文書・図像類
Title: Well-Structured Pushdown Systems, Part 1: Decidable Classes for Coverability
Author/Editor: Cai, Xiaojuan
Ogawa, Mizuhito
Author Heading: Cai, Xiaojuan
Ogawa, Mizuhito
Publication, Distribution, etc.: 北陸先端科学技術大学院大学情報科学研究科
Publication Date: 2013-01-08
Publication Date (W3CDTF): 2013-01-08
Periodical title: Research report (School of Information Science, Japan Advanced Institute of Science and Technology)
No. or year of volume/issue: IS-RR-2013-001
Volume: IS-RR-2013-001
Pages: 1-19
ISSN (Periodical Title): ISSN : 0918-7553
Text Language Code: eng
Target Audience: 一般
Note (General): Pushdown systems (PDSs) nicely model single-thread recursive programs, and well-structured transition systems (WSTS), such as vector addition systems, are useful to represent non-recursive multithread programs. Our goal is to investigate well-structured pushdown systems (WSPDSs), pushdown systems with well-quasi-ordered control states and stack alphabet, to combine these ideas. This paper focuses on decidable classes of coverability and extends Pautomata techniques for configuration reachability of PDSs to those for coverability of WSPDSs, in forward and backward ways. A Post^*-automata (resp. Pre^*-automata) construction is combined with Karp-Miller acceleration (resp. ideal representation) to characterize the set of successors (resp. predecessors) of given configurations. We show decidability results of coverability, which include recursive vector addition system with states [1], multi-set pushdown systems [2, 3], and a WSPDS with finite control states and well-quasi-ordered stack alphabet.
リサーチレポート（北陸先端科学技術大学院大学情報科学研究科）
identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/11347
Access Restrictions: 限定公開
Data Provider (Database): 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）
https://irdb.nii.ac.jp
Original Data Provider (Database): 北陸先端科学技術大学院大学 : JAIST学術研究成果リポジトリ