Scholarlink

Determinizing a nondeterministic input-driven pushdown automaton (NIDPDA) of size n results in the worst case in a machine of size \(2^{\varTheta (n^2)}\) (R. Alur, P. Madhusudan, “Adding nesting structure to words”, J.ACM 56(3), 2009). A significantly improved determinization upper bound is known for k-path NIDPDAs that can have at most k computations on any input. We improve the known upper bound of determinization of k-path NIDPDAs by, roughly speaking, making the deterministic input-driven machine (DIDPDA) remember the shape of the tree in which the nondeterministic choices were made. Also we provide upper bounds for converting k-path universal input driven pushdown automata to DIDPDAs and establish lower bounds.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Improved Upper Bounds for Determinizing NIDPDAs with Limited Nondeterminism

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Mohammad Zakzok,
  • Kai Salomaa

摘要

Determinizing a nondeterministic input-driven pushdown automaton (NIDPDA) of size n results in the worst case in a machine of size \(2^{\varTheta (n^2)}\) (R. Alur, P. Madhusudan, “Adding nesting structure to words”, J.ACM 56(3), 2009). A significantly improved determinization upper bound is known for k-path NIDPDAs that can have at most k computations on any input. We improve the known upper bound of determinization of k-path NIDPDAs by, roughly speaking, making the deterministic input-driven machine (DIDPDA) remember the shape of the tree in which the nondeterministic choices were made. Also we provide upper bounds for converting k-path universal input driven pushdown automata to DIDPDAs and establish lower bounds.