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 letter-bounded languages are considered. It turns out 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.
Descriptional Complexity of Bounded Context-Free Languages / A. Malcher, G. Pighizzini - In: Developments in Language Theory : 11th International Conference, DLT 2007, Turku, Finland, July 3-6, 2007 : Proceedings / [a cura di] Tero Harju, Juhani Karhumäk, Arto Lepistö (Eds.). - Berlin : Springer, 2007. - ISBN 9783540732075. - pp. 312-323 (( Intervento presentato al 11. convegno Developments in Language Theory tenutosi a Turku, Finland nel 2007 [10.1007/978-3-540-73208-2_30].
Descriptional Complexity of Bounded Context-Free Languages
G. PighizziniUltimo
2007
Abstract
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 letter-bounded languages are considered. It turns out 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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.