## Abstract

It is known that a nondeterministic input-driven pushdown automaton (IDPDA) (a.k.a. visibly pushdown automaton; a.k.a. nested word automaton) with n states can be transformed to an equivalent deterministic automaton with 2^{Θ}(n^{2}) states (B. von Braunmühl and R. Verbeek, 1983 [8]), and that this size is necessary in the worst case (R. Alur and P. Madhusudan, 2009 [4]). This paper demonstrates that the same worst-case 2^{Θ}(n^{2}) size blow-up occurs when converting a nondeterministic IDPDA to an unambiguous one, and an unambiguous IDPDA to a deterministic one. In addition, the methods developed in this paper are used to demonstrate that the descriptional complexity of complementation for nondeterministic IDPDAs is 2^{Θ}(n^{2}), and that the descriptional complexity of homomorphisms for deterministic IDPDAs is 2^{Θ}(n^{2}).

Original language | English |
---|---|

Pages (from-to) | 1-11 |

Number of pages | 11 |

Journal | Theoretical Computer Science |

Volume | 566 |

Issue number | C |

DOIs | |

Publication status | Published - 1 Jan 2015 |

## Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)