The Library
Adaptive synchronisation of pushdown automata
Tools
Balasubramanian, A. R. and Thejaswini, K. S. (2021) Adaptive synchronisation of pushdown automata. In: 32nd International Conference on Concurrency Theory (CONCUR 2021), Paris, France, 23-27 Aug 2021. Published in: 32nd International Conference on Concurrency Theory (CONCUR 2021), 203 17:1-17:15. ISBN 9783959772037. doi:10.4230/LIPIcs.CONCUR.2021.17 ISSN 1868-8969.
|
PDF
WRAP-Adaptive-synchronisation-pushdown-automata-2021.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (898Kb) | Preview |
Official URL: https://drops.dagstuhl.de/opus/volltexte/2021/1439...
Abstract
We introduce the notion of adaptive synchronisation for pushdown automata, in which there is an external observer who has no knowledge about the current state of the pushdown automaton, but can observe the contents of the stack. The observer would then like to decide if it is possible to bring the automaton from any state into some predetermined state by giving inputs to it in an adaptive manner, i.e., the next input letter to be given can depend on how the contents of the stack changed after the current input letter. We show that for non-deterministic pushdown automata, this problem is 2-EXPTIME-complete and for deterministic pushdown automata, we show EXPTIME-completeness.
To prove the lower bounds, we first introduce (different variants of) subset-synchronisation and show that these problems are polynomial-time equivalent with the adaptive synchronisation problem. We then prove hardness results for the subset-synchronisation problems. For proving the upper bounds, we consider the problem of deciding if a given alternating pushdown system has an accepting run with at most k leaves and we provide an n^O(k²) time algorithm for this problem.
Item Type: | Conference Item (Paper) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics T Technology > TA Engineering (General). Civil engineering (General) |
|||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
Library of Congress Subject Headings (LCSH): | Smart materials, Machine theory, Sequential machine theory | |||||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||
Journal or Publication Title: | 32nd International Conference on Concurrency Theory (CONCUR 2021) | |||||||||
Publisher: | Schloss Dagstuhl — Leibniz-Zentrum für Informatik | |||||||||
Place of Publication: | Dagstuhl, Germany | |||||||||
ISBN: | 9783959772037 | |||||||||
ISSN: | 1868-8969 | |||||||||
Official Date: | 13 August 2021 | |||||||||
Dates: |
|
|||||||||
Volume: | 203 | |||||||||
Page Range: | 17:1-17:15 | |||||||||
DOI: | 10.4230/LIPIcs.CONCUR.2021.17 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||
Date of first compliant deposit: | 20 September 2021 | |||||||||
Date of first compliant Open Access: | 21 September 2021 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Conference Paper Type: | Paper | |||||||||
Title of Event: | 32nd International Conference on Concurrency Theory (CONCUR 2021) | |||||||||
Type of Event: | Conference | |||||||||
Location of Event: | Paris, France | |||||||||
Date(s) of Event: | 23-27 Aug 2021 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year