Journal article

Publication year: 2012

Pages: 119-133

Journal: Theoretical Computer Science

Volume number: 449

ISSN: 0304-3975

DOI Link: https://doi.org/10.1016/j.tcs.2012.04.007

Publisher: Elsevier

Abstract: 
Two-way nondeterministic pushdown automata (2PDA) are classical nondeterministic pushdown automata (PDA) enhanced with two-way motion of the input head. In this paper, the subclass of 2PDA accepting bounded languages and making at most a constant number of input head turns is studied with respect to descriptional complexity aspects. In particular, the effect of reducing the number of pushdown reversals to a constant number is of interest. It turns out that this reduction leads to an exponential blow-up in case of nondeterministic devices, and to a doubly-exponential blow-up in case of deterministic devices. If the restriction On boundedness of the languages considered and on the finiteness of the number of head and pushdown turns is dropped, the resulting trade-offs are no longer bounded by recursive functions, and so-called non-recursive trade-offs are shown. (C) 2012 Elsevier B.V. All rights reserved.

Harvard Citation style: Malcher, A., Mereghetti, C. and Palano, B. (2012) Descriptional complexity of two-way pushdown automata with restricted head reversals, Theoretical Computer Science, 449, pp. 119-133. https://doi.org/10.1016/j.tcs.2012.04.007

APA Citation style: Malcher, A., Mereghetti, C., & Palano, B. (2012). Descriptional complexity of two-way pushdown automata with restricted head reversals. Theoretical Computer Science. 449, 119-133. https://doi.org/10.1016/j.tcs.2012.04.007