Descriptional complexity of unambiguous input-driven pushdown automata

Thumbnail Image
Date
2015-04
Authors
Okhotin, Alexander
Salomaa, Kai
Keyword
automata theory, descriptional complexity
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.
External DOI