Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2013.313
URN: urn:nbn:de:0030-drops-43829
URL: https://drops.dagstuhl.de/opus/volltexte/2013/4382/
Hague, Matthew
Saturation of Concurrent Collapsible Pushdown Systems
| pdf-format: |
|
Abstract
Multi-stack pushdown systems are a well-studied model of concurrent computation using threads with first-order procedure calls. While, in general, reachability is undecidable, there are numerous restrictions on stack behaviour that lead to decidability. To model higher-order procedures calls, a generalisation of pushdown stacks called collapsible pushdown stacks are required. Reachabilityproblems for multi-stack collapsible pushdown systems have been little studied. Here, we study ordered, phase-bounded and scope-bounded multi-stack collapsible pushdown systems using saturation techniques, showing decidability of control state reachability and giving a regular representation of all configurations that can reach a given control state.
BibTeX - Entry
@InProceedings{hague:LIPIcs:2013:4382,
author = {Matthew Hague},
title = {{Saturation of Concurrent Collapsible Pushdown Systems}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {313--325},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Anil Seth and Nisheeth K. Vishnoi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/4382},
URN = {urn:nbn:de:0030-drops-43829},
doi = {10.4230/LIPIcs.FSTTCS.2013.313},
annote = {Keywords: Concurrency, Automata, Higher-Order, Verification, Model-Checking}
}
| Keywords: | Concurrency, Automata, Higher-Order, Verification, Model-Checking | |
| Seminar: | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) | |
| Issue date: | 2013 | |
| Date of publication: | 10.12.2013 |
