Descriptional complexity of unambiguous input-driven pushdown automata

dc.contributor.authorOkhotin, Alexanderen
dc.contributor.authorSalomaa, Kaien
dc.date.accessioned2017-07-17T14:51:01Z
dc.date.available2017-07-17T14:51:01Z
dc.date.issued2015-04
dc.description.abstractIt 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.en
dc.description.sponsorshipNatural Sciences and Engineering Research Council of Canadaen
dc.identifier.citationTheoretical Computer Science, Vol. 566, 2015, pp. 1-11en
dc.identifier.urihttp://hdl.handle.net/1974/15960
dc.language.isoenen
dc.publisherTheoretical Computer Scienceen
dc.subjectautomata theory, descriptional complexityen
dc.titleDescriptional complexity of unambiguous input-driven pushdown automataen
dc.typejournal articleen
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
idpdaQS.pdf
Size:
529.5 KB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
3.77 KB
Format:
Item-specific license agreed upon to submission
Description: