Reachability problems in low-dimensional nondeterministic polynomial maps over integers

DOI10.1016/j.ic.2021.104785OpenAlexW3178445979MaRDI QIDQ2051802

Sang-Ki Ko, Reino Niskanen, Igor Potapov

Publication date: 25 November 2021

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2021.104785

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

What else is undecidable about loops?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Iterated maps on the interval as dynamical systems
• Occurrence of zero in a linear recursive sequence
• Remarks on blind and partially blind one-way multicounter machines
• A polynomial time algorithm for diophantine equations in one variable
• Computability with low-dimensional dynamical systems
• Reachability problems in nondeterministic polynomial maps on the integers
• Reachability problem for polynomial iteration is PSPACE-complete
• Decision problems for semi-Thue systems with a few rules
• On undecidability bounds for matrix decision problems
• On the complexity of bounded time and precision reachability for piecewise affine systems
• Context-free commutative grammars with integer counters and resets
• Improved matrix pair undecidability results
• Reachability Problems for PAMs
• The Invariance Problem for Matrix Semigroups
• Reachability in Register Machines with Polynomial Updates
• Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words
• UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
• Reachability Problems for One-Dimensional Piecewise Affine Maps
• Integer Vector Addition Systems with States
• REACHABILITY PROBLEMS IN LOW-DIMENSIONAL ITERATIVE MAPS
• The Target Discounted-Sum Problem
• Reducibility among Combinatorial Problems
• Unboundedness Problems for Languages of Vector Addition Systems.
• On Affine Reachability Problems
• Decidability of membership problems for flat rational subsets of GL(2, Q) and singular matrices
• Mortality of iterated piecewise affine functions over the integers: Decidability and complexity
• A variant of a recursively unsolvable problem
• A survey of computational complexity results in systems and control
• Deciding stability and mortality of piecewise affine dynamical systems

This page was built for publication: Reachability problems in low-dimensional nondeterministic polynomial maps over integers