Affine extensions of integer vector addition systems with states

DOI10.4230/LIPICS.CONCUR.2018.14MaRDI QIDQ5009428zbMATH OpenFDO

Authors Michael Blondin, Christoph Haase, Filip Mazowiecki

Publication date 4 August 2021

Full work available at URL https://doi.org/10.4230/LIPICS.CONCUR.2018.14

zbMATH Keywords

affine transformationscomputational complexityreachabilitysemilinear setsvector addition systems

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• The complexity of reachability in affine vector addition systems with states
• Integer vector addition systems with states
• Reachability in two-dimensional vector addition systems with states is PSPACE-complete
• Polynomial vector addition systems with states
• CONCUR 2004 - Concurrency Theory

Cites work

• An Algorithm for the General Petri Net Reachability Problem
• An SMT-based approach to coverability analysis
• Bounded Parikh automata
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Decision problems for additive regular functions
• Finite Groups of Matrices Whose Entries Are Integers
• How hard is it to verify flat affine counter systems with the finite monoid property?
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1223710 (Why is no real title available?)
• scientific article; zbMATH DE number 1954380 (Why is no real title available?)
• scientific article; zbMATH DE number 1392309 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• Integer vector addition systems with states
• Logics for continuous reachability in Petri nets and vector addition systems with states
• On finite semigroups of matrices
• On the reachability problem for 5-dimensional vector addition systems
• Parallel program schemata
• Reachability in Petri nets with inhibitor arcs
• Reachability in two-dimensional vector addition systems with states is PSPACE-complete
• Regular combinators for string transformations
• Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
• Some decision problems related to the reachability problem for Petri nets
• The covering and boundedness problems for vector addition systems
• The taming of the semi-linear set
• Unambiguous constrained automata
• Unbounded-thread program verification using thread-state equations

Cited in

(12)

• On decidability and complexity of low-dimensional robot games
• Reachability problems in low-dimensional nondeterministic polynomial maps over integers
• Directed reachability for infinite-state systems
• Integer vector addition systems with states
• The complexity of reachability in affine vector addition systems with states
• Affine extensions of integer vector addition systems with states
• scientific article; zbMATH DE number 7407775 (Why is no real title available?)
• Weak cost register automata are still powerful
• Expressive Power of Broadcast Consensus Protocols
• Integer Weighted Automata on Infinite Words
• On the size of finite rational matrix semigroups
• Integer weighted automata on infinite words

This page was built for publication: Affine extensions of integer vector addition systems with states

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