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

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.
Original languageEnglish
Article number106135
JournalInformation Processing Letters
Volume171
ISSN0020-0190
DOIs
Publication statusPublished - Oct 2021

    Research areas

  • Pushdown systems, One-counter systems, Dyck reachability, Formal languages

See relations at Aarhus University Citationformats

ID: 216037408