The complexity of bidirected reachability in valence systems

DOI10.1145/3531130.3533345MaRDI QIDQ6649456

Georg Zetzsche, Moses Ganardi, Rupak Majumdar

Publication date: 6 December 2024

zbMATH Keywords

complexityreachabilityreversiblecountersvector addition systemsInfinite-state systemspushdownbidirected

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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