Descriptional complexity of unambiguous input-driven pushdown automata

Abstract

It is known that a nondeterministic input-driven pushdown automaton (IDPDA) (a.k.a.~visibly pushdown automaton; a.k.a.~nested word automaton) of size $n$ can be transformed to an equivalent deterministic automaton of size $2^{\Theta(n^2)}$ (B. von Braunm"uhl, R. Verbeek, \href{http://dx.doi.org/10.1016/S0304-0208(08)73072-X} {Input-driven languages are recognized in $\log n$ space''}, FCT 1983), and that this size is necessary in the worst case (R. Alur, P. Madhusudan, \href{http://dx.doi.org/10.1145/1516512.1516518} {Adding nesting structure to words''}, J.ACM, 2009). This paper demonstrates that the same worst-case $2^{\Theta(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^{\Theta(n^2)}$, and that the descriptional complexity of homomorphisms for deterministic IDPDAs is $2^{\Theta(n^2)}$ as well.