Descriptional complexity of unambiguous input-driven pushdown automata
Loading...
Authors
Okhotin, Alexander
Salomaa, Kai
Date
2015-04
Type
journal article
Language
en
Keyword
automata theory, descriptional complexity
Alternative Title
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.
Description
Citation
Theoretical Computer Science, Vol. 566, 2015, pp. 1-11
Publisher
Theoretical Computer Science