Adaptive synchronisation of pushdown automata
AR Balasubramanian, KS Thejaswini - arXiv preprint arXiv:2102.06897, 2021 - arxiv.org
arXiv preprint arXiv:2102.06897, 2021•arxiv.org
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\emph {adaptive} manner, ie, 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 …
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\emph {adaptive} manner, ie, 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 …
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 \emph{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 leaves and we provide an time algorithm for this problem.
arxiv.org
以上显示的是最相近的搜索结果。 查看全部搜索结果