2009/05/07 by Andreas Malcher, Malcher, Andreas, Giovanni Pighizzini +1
Computer Science · #F.1.1 #F.2.3 #F.4.2 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL
paper · pdf · doi:10.48550/arxiv.0905.1045
31 pages, 1 figure. A preliminary version was presented at DLT 2007. The full version is submitted to a journal
arxiv created 2009/05/08 · arxiv updated 2009/12/01
Finite-turn pushdown automata (PDA) are investigated concerning their descriptional complexity. It is known that they 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, finite-turn PDAs accepting bounded languages are considered. First, letter-bounded languages are studied. We prove that in this case the non-recursive trade-off is reduced to a recursive trade-off, more precisely, to an exponential trade-off. A conversion algorithm is presented and the optimality of the construction is shown by proving tight lower bounds. Furthermore, the question of reducing the number of turns of a given finite-turn PDA is studied. Again, a conversion algorithm is provided which shows that in this case the trade-off is at most polynomial. Finally, the more general case of word-bounded languages is investigated. We show how the results obtained for letter-bounded languages can be extended to word-bounded languages.