Copertina

The Tractability Border of Reachability in Simple Vector Addition Systems with States

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Chistikov, Dmitry, Czerwiński, Wojciech, Mazowiecki, Filip, Orlikowski, Łukasz, Sinclair-Banks, Henry, Węgrzycki, Karol
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Formal Languages and Automata Theory Logic in Computer Science
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

Invariants for One-Counter Automata with Disequality Tests
di: Chistikov, Dmitry, et al.
Pubblicazione: (2024)

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

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

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

Reachability in One-Dimensional Pushdown Vector Addition Systems is Decidable
di: Bizière, Clotilde, et al.
Pubblicazione: (2024)

Exploring VASS Parameterised by Geometric Dimension
di: Czerwiński, Wojciech, et al.
Pubblicazione: (2026)

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

Fine-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs
di: Drabik, Karolina, et al.
Pubblicazione: (2025)

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

Intersecting Dense Automata
di: Chistikov, Dmitry, et al.
Pubblicazione: (2026)

Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata
di: Jecker, Ismaël, et al.
Pubblicazione: (2023)

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

A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter
di: Shakiba, Yousef, et al.
Pubblicazione: (2025)

Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata
di: Mazowiecki, Filip, et al.
Pubblicazione: (2025)

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

Improved Algorithm for Reachability in $d$-VASS
di: Fu, Yuxi, et al.
Pubblicazione: (2024)

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

Uncertainty Removal in Verification of Nonlinear Systems against Signal Temporal Logic via Incremental Reachability Analysis
di: Besset, Antoine, et al.
Pubblicazione: (2025)

History-Constrained Systems
di: Kuijer, Louwe B., et al.
Pubblicazione: (2026)

A Completeness Theorem for Probabilistic Regular Expressions
di: Różowski, Wojciech, et al.
Pubblicazione: (2023)

Soundness of reset workflow nets
di: Blondin, Michael, et al.
Pubblicazione: (2025)

Simple grammar bisimilarity, with an application to session type equivalence
di: Poças, Diogo, et al.
Pubblicazione: (2024)

Some properties of $β$-$η$-normal forms in $λ$-K-calculus (Alcune proprietá delle forme $β$-$η$-normali nel $λ$-K-calcolo)
di: Böhm, Corrado, et al.
Pubblicazione: (2025)

First-Order Intuitionistic Linear Logic and Hypergraph Languages
di: Pshenitsyn, Tikhon
Pubblicazione: (2025)

A Diamond Structure in the Transducer Hierarchy
di: Kaufmann, Noah
Pubblicazione: (2021)

Reachability in Geometrically $d$-Dimensional VASS
di: Fu, Yuxi, et al.
Pubblicazione: (2025)

Bi-reachability in Petri nets with data
di: Kamiński, Łukasz, et al.
Pubblicazione: (2024)

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

PVASS Reachability is Decidable
di: Guttenberg, Roland, et al.
Pubblicazione: (2025)

Weighted GKAT: Completeness and Complexity
di: Van Koevering, Spencer, et al.
Pubblicazione: (2025)

A Diagrammatic Axiomatisation of Behavioural Distance of Nondeterministic Processes
di: Różowski, Wojciech, et al.
Pubblicazione: (2026)

Unreliability in Practical Subclasses of Communicating Systems
di: Suresh, Amrita, et al.
Pubblicazione: (2025)

General Decidability Results for Systems with Continuous Counters
di: Balasubramanian, A. R., et al.
Pubblicazione: (2025)

A Session Type System for Asynchronous Unreliable Broadcast Communication
di: Kouzapas, Dimitrios, et al.
Pubblicazione: (2019)

Monitorability for the Modal mu-Calculus over Systems with Data: From Practice to Theory
di: Aceto, Luca, et al.
Pubblicazione: (2025)

A cyclic proof system for Guarded Kleene Algebra with Tests (full version)
di: Rooduijn, Jan, et al.
Pubblicazione: (2024)

A proof theory of right-linear (omega-)grammars via cyclic proofs
di: Das, Anupam, et al.
Pubblicazione: (2024)