Computer Science – Formal Languages and Automata Theory
Scientific paper
2009-05-07
Computer Science
Formal Languages and Automata Theory
31 pages, 1 figure. A preliminary version was presented at DLT 2007. The full version is submitted to a journal
Scientific paper
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.
Malcher Andreas
Pighizzini Giovanni
No associations
LandOfFree
Descriptional complexity of bounded context-free languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Descriptional complexity of bounded context-free languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Descriptional complexity of bounded context-free languages will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-455772