Reachability problems in low-dimensional nondeterministic polynomial maps over integers

DOI10.1016/J.IC.2021.104785OpenAlexW3178445979MaRDI QIDQ2051802FDOQ2051802

Authors: 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

Recommendations

• Reachability problems in nondeterministic polynomial maps on the integers
• REACHABILITY PROBLEMS IN LOW-DIMENSIONAL ITERATIVE MAPS
• Reachability problem for polynomial iteration is PSPACE-complete
• About the decision of reachability for register machines
• On reachability problem in 1-dimensional 2-interval piecewise-affine mappings

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Reducibility among Combinatorial Problems
• Title not available (Why is that?)
• A variant of a recursively unsolvable problem
• Remarks on blind and partially blind one-way multicounter machines
• Decision problems for semi-Thue systems with a few rules
• A survey of computational complexity results in systems and control
• Undecidability bounds for integer matrices using Claus instances
• Computability with low-dimensional dynamical systems
• REACHABILITY PROBLEMS IN LOW-DIMENSIONAL ITERATIVE MAPS
• Deciding stability and mortality of piecewise affine dynamical systems
• Iterated maps on the interval as dynamical systems
• Occurrence of zero in a linear recursive sequence
• A polynomial time algorithm for diophantine equations in one variable
• Integer Vector Addition Systems with States
• Title not available (Why is that?)
• Improved matrix pair undecidability results
• Title not available (Why is that?)
• Reachability in register machines with polynomial updates
• Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words
• Title not available (Why is that?)
• On undecidability bounds for matrix decision problems
• Title not available (Why is that?)
• Reachability problems in nondeterministic polynomial maps on the integers
• Reachability problem for polynomial iteration is PSPACE-complete
• Context-free commutative grammars with integer counters and resets
• On the complexity of bounded time and precision reachability for piecewise affine systems
• Reachability Problems for PAMs
• The Invariance Problem for Matrix Semigroups
• Reachability Problems for One-Dimensional Piecewise Affine Maps
• The Target Discounted-Sum Problem
• Unboundedness Problems for Languages of Vector Addition Systems.
• On Affine Reachability Problems
• Title not available (Why is that?)
• 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

Cited In (5)

• Comments on ``Reachability of polynomial matrix descriptions (PMDs) by G. F. Fragulis and A. I. G. Vardulakis
• Reachability problems in nondeterministic polynomial maps on the integers
• About the decision of reachability for register machines
• REACHABILITY PROBLEMS IN LOW-DIMENSIONAL ITERATIVE MAPS
• What else is undecidable about loops?

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

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