×

Towards exact state complexity bounds for input-driven pushdown automata. (English) Zbl 1517.68201

Hoshi, Mizuho (ed.) et al., Developments in language theory. 22nd international conference, DLT 2018, Tokyo, Japan, September 10–14, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11088, 441-452 (2018).
Summary: The paper improves several state complexity bounds for input-driven pushdown automata (IDPDA), also known as visibly pushdown automata. For deterministic IDPDA it is proved that the number of states sufficient and in the worst case necessary to represent the reversal of an \(n\)-state automaton is exactly \(n^n\) if all inputs are assumed to be well-nested, and between \(n^n\) and \(n(n^n-(n-1)^n)+1\) without this restriction, cf. \(2^{\varTheta(n\log n)}\) in the literature. For the concatenation of an \(m\)-state and an \(n\)-state IDPDA, the new lower bound is \(mn^n\), which is asymptotically tight for well-nested inputs. Without this restriction, the state complexity is between \(mn^n\) and \(m(n+1)n^n2^n\). Finally, it is proved that transforming an \(n\)-state nondeterministic IDPDA to a deterministic one requires exactly \(2^{n^2}\) states, cf. \(2^{\varTheta (n^2)}\) in the literature; the known lower bounds on complementing nondeterministic IDPDA and on transforming them to unambiguous are also improved.
For the entire collection see [Zbl 1398.68030].

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI