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. Pighizzini
Ultimo
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.
Automata and formal languages; Bounded languages; Descriptional complexity; Finite-turn pushdown automata; Recursive trade-offs
Settore INF/01 - Informatica
2007
Book Part (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/34975
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 3
social impact