کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951223 | 1441196 | 2017 | 26 صفحه PDF | دانلود رایگان |
- We look at the complexity of reachability for automata over infinite alphabets equipped with registers and a stack.
- We show that local reachability is EXPTIME-complete.
- We give an EXPTIME saturation algorithm for global reachability.
- We show that reachability is undecidable for higher-order register pushdown automata even at order 2.
We investigate reachability in pushdown automata over infinite alphabets. We show that, in terms of reachability/emptiness, these machines can be faithfully represented using only 3r elements of the alphabet, where r is the number of registers. We settle the complexity of associated reachability/emptiness problems. In contrast to register automata, the emptiness problem for pushdown register automata is EXPTIME-complete, independent of the register storage policy used. We also solve the global reachability problem by representing pushdown configurations with a special register automaton. Finally, we examine extensions of pushdown storage to higher orders and show that reachability is undecidable at order 2.
Journal: Journal of Computer and System Sciences - Volume 87, August 2017, Pages 58-83