Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950648 | Information and Computation | 2017 | 18 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Zuzana Bednárová, Viliam Geffert,