Shortest Paths in One-Counter Systems

DOI10.1007/978-3-662-49630-5_27zbMATH Open1475.68147arXiv1510.05460OpenAlexW2215731810MaRDI QIDQ2811358FDOQ2811358

Piotr Hofman, Michael Wehar, Dmitry Chistikov, Wojciech Czerwiński, Michał Pilipczuk

Publication date: 10 June 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We show that any one-counter automaton with $n$ states, if its language is non-empty, accepts some word of length at most $O(n^2)$. This closes the gap between the previously known upper bound of $O(n^3)$ and lower bound of $Omega(n^2)$. More generally, we prove a tight upper bound on the length of shortest paths between arbitrary configurations in one-counter transition systems (weaker bounds have previously appeared in the literature).

Full work available at URL: https://arxiv.org/abs/1510.05460

Recommendations

• Shortest Paths in One-Counter Systems
• Shortest paths in reachability graphs
• scientific article; zbMATH DE number 3105908
• Computing almost shortest paths
• Shortest paths in almost acyclic graphs
• Shortest paths in Sierpiński graphs
• Computing shortest paths in networks derived from recurrence relations
• The complexity of rerouting shortest paths
• The complexity of rerouting shortest paths

zbMATH Keywords

shortest pathone-counter automatonone-counter system

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics in computer science (68R05)

Cites Work

• Introduction to algorithms
• Title not available (Why is that?)
• Streaming transducers for algorithmic verification of single-pass list-processing programs
• Rational indexes of generators of the cone of context-free languages
• Reachability analysis of pushdown automata: Application to model-checking
• Automatic verification of recursive procedures with one integer parameter.
• Term Rewriting and Applications
• The effects of bounding syntactic resources on Presburger LTL
• The Reachability Problem over Infinite Graphs
• Demystifying Reachability in Vector Addition Systems
• Langages à un compteur
• Decidability of Weak Simulation on One-Counter Nets
• The rational index of the Dyck language \(D_ 1^{'*}\)
• Shortest Paths in One-Counter Systems
• Notes on counting with finite machines
• Equivalence of deterministic one-counter automata is NL-complete
• Proofs that count
• Upper Bounds for Newton’s Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata
• Witness Runs for Counter Machines

Cited In (9)

• Title not available (Why is that?)
• Rational index of languages defined by grammars with bounded dimension of parse trees
• Title not available (Why is that?)
• Countdown games, and simulation on (succinct) one-counter nets
• Shortest accepted strings for two-way finite automata: approaching the \(2^n\) lower bound
• On the Length of Shortest Strings Accepted by Two-way Finite Automata
• Bounded Context Switching for Valence Systems
• Shortest Paths in One-Counter Systems
• Rational index of languages with bounded dimension of parse trees

Uses Software

• ARMC

This page was built for publication: Shortest Paths in One-Counter Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2811358)