On Affine Reachability Problems

DOI10.4230/LIPICS.MFCS.2020.48MaRDI QIDQ5089216zbMATH OpenOpenAlexFDO

Authors Stefan Jaax, Stefan Kiefer

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/1905.05114

zbMATH Keywords

counter machinesmatrix semigroupsreachability

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Bound on Solutions of Linear Integer Equalities and Inequalities
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Decidability of the membership problem for \(2\times 2\) integer matrices
• Decision problems for linear recurrence sequences
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Integer vector addition systems with states
• Membership Problem for the Modular Group
• Mortality for 2 2 matrices is NP-hard
• Mortality of iterated piecewise affine functions over the integers: decidability and complexity
• Mortality Problem for 2×2 Integer Matrices
• On the complexity of the orbit problem
• Reachability in register machines with polynomial updates
• Reachability in two-clock timed automata is PSPACE-complete
• Reachability problem for polynomial iteration is PSPACE-complete
• Reachability problems for one-dimensional piecewise affine maps
• REACHABILITY PROBLEMS IN LOW-DIMENSIONAL ITERATIVE MAPS
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Some decision problems on integer matrices
• The complexity of reachability in affine vector addition systems with states
• The identity problem for matrix semigroups in \(\mathrm{SL}_2(\mathbb{Z})\) is NP-complete
• The mortality problem for matrices of low dimensions
• The reachability problem for Petri nets is not elementary
• Undecidability in binary tag systems and the Post correspondence problem for five pairs of words
• Unsolvability in 3 × 3 Matrices

Cited in

(7)

• Reachability problems in low-dimensional nondeterministic polynomial maps over integers
• An algebraic view on p-admissible concrete domains for lightweight description logics
• On the complexity of bounded time and precision reachability for piecewise affine systems
• Reachability of Affine Systems on Polytopes
• scientific article; zbMATH DE number 1794363 (Why is no real title available?)
• scientific article; zbMATH DE number 2144766 (Why is no real title available?)
• Hybrid Systems: Computation and Control

This page was built for publication: On Affine Reachability Problems

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