The complexity of bidirected reachability in valence systems
From MaRDI portal
Publication:6649456
DOI10.1145/3531130.3533345MaRDI QIDQ6649456
Georg Zetzsche, Moses Ganardi, Rupak Majumdar
Publication date: 6 December 2024
complexityreachabilityreversiblecountersvector addition systemsInfinite-state systemspushdownbidirected
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The Nielsen reduction and P-complete problems in free groups
- The submonoid and rational subset membership problems for graph groups.
- Knapsack in graph groups
- The complexity of the word problems for commutative semigroups and polynomial ideals
- The complexity of matrix rank and feasible systems of linear equations
- The emptiness problem for valence automata over graph monoids
- Recent advances on reachability problems for valence systems (invited talk)
- Semilinearity and Context-Freeness of Languages Accepted by Valence Automata
- Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth
- Computing Downward Closures for Stacked Counter Automata
- The rational subset membership problem for groups: a survey
- The Reachability Problem for Vector Addition System with One Zero-Test
- Subcubic algorithms for recursive state machines
- When Is a Graph Product of Groups Virtually-Free?
- SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE
- Integer Vector Addition Systems with States
- On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension
- Undirected connectivity in log-space
- Algorithms for the Solution of Systems of Linear Diophantine Equations
- Algebraic Potential Theory on Graphs
- First-order logic with reachability for infinite-state systems
- FOLDINGS, GRAPHS OF GROUPS AND THE MEMBERSHIP PROBLEM
- Reachability in Petri Nets with Inhibitor Arcs
- Bounded Context Switching for Valence Systems
- The complexity of the coverability, the containment, and the equivalence problems for commutative semigroups
- An automata theoretic approach to the generalized word problem in graphs of groups
- Silent Transitions in Automata with Storage
- Context-sensitive data-dependence analysis via linear conjunctive language reachability
- Automated Deduction – CADE-20
- A compendium of problems complete for symmetric logarithmic space
- Scope-Bounded Reachability in Valence Systems
This page was built for publication: The complexity of bidirected reachability in valence systems
