Aarhus University Seal / Aarhus Universitets segl

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

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Standard

Tight bounds for reachability problems on one-counter and pushdown systems. / Hansen, Jakob Cetti; Kjelstrøm, Adam Husted; Pavlogiannis, Andreas.

In: Information Processing Letters, Vol. 171, 106135, 10.2021.

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Harvard

APA

CBE

MLA

Vancouver

Author

Bibtex

@article{94b624d4ee6a4a60989383bc06ba9cfb,
title = "Tight bounds for reachability problems on one-counter and pushdown systems",
abstract = "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.",
keywords = "Pushdown systems, One-counter systems, Dyck reachability, Formal languages",
author = "Hansen, {Jakob Cetti} and Kjelstr{\o}m, {Adam Husted} and Andreas Pavlogiannis",
year = "2021",
month = oct,
doi = "10.1016/j.ipl.2021.106135",
language = "English",
volume = "171",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier BV",

}

RIS

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

U2 - 10.1016/j.ipl.2021.106135

DO - 10.1016/j.ipl.2021.106135

M3 - Journal article

VL - 171

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

M1 - 106135

ER -