Article ID Journal Published Year Pages File Type
4950648 Information and Computation 2017 18 Pages PDF
Abstract
We shall consider nondeterministic and deterministic automata equipped with a limited pushdown (constant height npdas and dpdas) as well as their two-way versions (constant height 2npdas and 2dpdas). We show two double-exponential gaps for these devices, namely, (i) for complementing constant height one-way npdas and (ii) for converting constant height 2npdas or 2dpdas into one-way devices.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,