Tight bounds for reachability problems on one-counter and pushdown systems

TY - JOUR

T1 - Tight bounds for reachability problems on one-counter and pushdown systems

AU - Hansen, Jakob Cetti

AU - Kjelstrøm, Adam Husted

AU - Pavlogiannis, Andreas

PY - 2021/10

Y1 - 2021/10

N2 - We consider the problem of reachability on One-Counter Systems (OCSs) and Pushdown Systems (PDSs). The problem has a well-known O(n3) bound on both models, while the bound is believed to be tight for PDSs. Here we establish new upper and lower bounds for reachability on OCSs and restricted PDSs. We show that the problem can be solved (i) in O(nω⋅log2⁡n) time on OCSs, and (ii) in O(n2) time on sparse PDSs when restricted to witness executions of stack height bounded by log⁡n. Moreover, we prove similar lower bounds.

AB - We consider the problem of reachability on One-Counter Systems (OCSs) and Pushdown Systems (PDSs). The problem has a well-known O(n3) bound on both models, while the bound is believed to be tight for PDSs. Here we establish new upper and lower bounds for reachability on OCSs and restricted PDSs. We show that the problem can be solved (i) in O(nω⋅log2⁡n) time on OCSs, and (ii) in O(n2) time on sparse PDSs when restricted to witness executions of stack height bounded by log⁡n. Moreover, we prove similar lower bounds.

KW - Pushdown systems

KW - One-counter systems

KW - Dyck reachability

KW - Formal languages

UR - http://www.scopus.com/inward/record.url?scp=85104580897&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2021.106135

DO - 10.1016/j.ipl.2021.106135

M3 - Journal article

SN - 0020-0190

VL - 171

JO - Information Processing Letters

JF - Information Processing Letters

M1 - 106135

ER -