Cover Image

Reachability in One-Dimensional Pushdown Vector Addition Systems is Decidable

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bizière, Clotilde, Czerwiński, Wojciech
Format:	Preprint
Published:	2024
Subjects:	Formal Languages and Automata Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Reachability in VASS Extended with Integer Counters
by: Bizière, Clotilde, et al.
Published: (2026)

Language Inclusion for Boundedly-Ambiguous Vector Addition Systems is Decidable
by: Czerwiński, Wojciech, et al.
Published: (2022)

Languages of Boundedly-Ambiguous Vector Addition Systems with States
by: Czerwiński, Wojciech, et al.
Published: (2025)

On the Reachability Problem for Two-Dimensional Branching VASS
by: Bizière, Clotilde, et al.
Published: (2025)

Reachability in Trace-Pushdown Systems
by: Köcher, Chris, et al.
Published: (2025)

The Tractability Border of Reachability in Simple Vector Addition Systems with States
by: Chistikov, Dmitry, et al.
Published: (2024)

Box-Reachability in Vector Addition Systems
by: Almagor, Shaull, et al.
Published: (2025)

Reachability and Related Problems in Vector Addition Systems with Nested Zero Tests
by: Guttenberg, Roland, et al.
Published: (2025)

Reasoning about Rare-Event Reachability in Stochastic Vector Addition Systems via Affine Vector Spaces
by: Jeppson, Joshua, et al.
Published: (2025)

Reachability in 3-VASS is Elementary
by: Czerwiński, Wojciech, et al.
Published: (2025)

Improving Reachability in Vector Addition Systems through Pumpability
by: Chen, Weijun, et al.
Published: (2026)

Reachability in Vector Addition System with States Parameterized by Geometric Dimension
by: Zheng, Yangluo
Published: (2024)

Input-Driven Pushdown Automata with Translucent Input Letters
by: Kutrib, Martin, et al.
Published: (2025)

Explorability in Pushdown Automata
by: Bedi, Ayaan, et al.
Published: (2025)

The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata
by: Yamakami, Tomoyuki
Published: (2021)

Visibly Pushdown Languages in Groups
by: Ciobanu, Laura, et al.
Published: (2026)

Continuous Pushdown VASS in One Dimension are Easy
by: Perez, Guillermo A., et al.
Published: (2024)

Language Equivalence is Undecidable in VASS with Restricted Nondeterminism
by: Czerwiński, Wojciech, et al.
Published: (2025)

Separability and Non-Determinizability of WSTS
by: Czerwiński, Wojciech, et al.
Published: (2023)

Deciding Subtyping for Asynchronous Multiparty Sessions
by: Li, Elaine, et al.
Published: (2024)

On Decidability and Expressive Power of Fusion Grammars
by: Pshenitsyn, Tikhon
Published: (2023)

A Bionic Natural Language Parser Equivalent to a Pushdown Automaton
by: Wei, Zhenghao, et al.
Published: (2024)

V-Star: Learning Visibly Pushdown Grammars from Program Inputs
by: Jia, Xiaodong, et al.
Published: (2024)

On Decidability Timed Automata with 2 Parametric Clocks
by: Bersani, Marcello M., et al.
Published: (2025)

On the Separability Problem of VASS Reachability Languages
by: Keskin, Eren, et al.
Published: (2024)

Completely Reachable Almost Group Automata
by: Torres, David Fernando Casas
Published: (2024)

Deciding Linear Height and Linear Size-to-Height Increase for Macro Tree Transducers
by: Gallot, Paul, et al.
Published: (2023)

Deciding whether an Attributed Translation can be realized by a Top-Down Transducer
by: Maneth, Sebastian, et al.
Published: (2023)

Flattability of Priority Vector Addition Systems
by: Guttenberg, Roland
Published: (2024)

On-The-Fly Algorithm for Reachability in Parametric Timed Games (Extended Version)
by: Dahlsen-Jensen, Mikael Bisgaard, et al.
Published: (2024)

Efficient Construction of Reachability Graphs for Petri Net Product Lines
by: Gómez-Martínez, Elena, et al.
Published: (2026)

PVASS Reachability is Decidable
by: Guttenberg, Roland, et al.
Published: (2025)

Deciding Reachability and the Covering Problem with Diagnostics for Sound Acyclic Free-Choice Workflow Nets
by: Prinz, Thomas M., et al.
Published: (2026)

Synchronous Signal Temporal Logic for Decidable Verification of Cyber-Physical Systems
by: Roop, Partha, et al.
Published: (2026)

Reachability in symmetric VASS
by: Kamiński, Łukasz, et al.
Published: (2025)

TARZAN: A Region-Based Library for Forward and Backward Reachability of Timed Automata (Extended Version)
by: Manini, Andrea, et al.
Published: (2026)

Well-Behaved (Co)algebraic Semantics of Regular Expressions in Dafny
by: Zetzsche, Stefan, et al.
Published: (2024)

Reachability Analysis of the Domain Name System
by: Nevatia, Dhruv, et al.
Published: (2024)

Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
by: Yamakami, Tomoyuki
Published: (2024)

A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
by: Guha, Shibashis, et al.
Published: (2021)