Journal article

Publication year: 2013

Pages: 1-20

Journal: Information and Computation

Volume number: 227

ISSN: 0890-5401

Open access status: Green

DOI Link: https://doi.org/10.1016/j.ic.2013.03.008

Publisher: Elsevier

Abstract: 
We investigate finite-turn pushdown automata (PDAs) from the point of view of descriptional complexity. It is known that such automata accept exactly the class of ultralinear context-free languages. Furthermore, the increase in size when converting arbitrary PDAs accepting ultralinear languages to finite-turn PDAs cannot be bounded by any recursive function. The latter phenomenon is known as non-recursive trade-off. In this paper, we consider finite-turn PDAs that can accept bounded languages. First, we study letter-bounded languages and prove that, in this case, the non-recursive trade-off is reduced to a recursive trade-off, more precisely, to an exponential trade-off. We present a conversion algorithm and show the optimality of the construction by proving tight lower bounds. Furthermore, we study the question of reducing the number of turns of a given finite-turn PDA. Again, we provide a conversion algorithm which shows that, in this case, the trade-off is at most polynomial. Finally, we investigate the more general case of word-bounded languages and show how the results obtained for letter-bounded languages can be extended to word-bounded languages. (C) 2013 Elsevier Inc. All rights reserved.

Harvard Citation style: Malcher, A. and Pighizzini, G. (2013) Descriptional complexity of bounded context-free languages, Information and Computation, 227, pp. 1-20. https://doi.org/10.1016/j.ic.2013.03.008

APA Citation style: Malcher, A., & Pighizzini, G. (2013). Descriptional complexity of bounded context-free languages. Information and Computation. 227, 1-20. https://doi.org/10.1016/j.ic.2013.03.008