Reachability problems in low-dimensional nondeterministic polynomial maps over integers

DOI10.1016/J.IC.2021.104785MaRDI QIDQ2051802OpenAlexFDO

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 53349 (Why is no real title available?)
• scientific article; zbMATH DE number 3628412 (Why is no real title available?)
• scientific article; zbMATH DE number 1339970 (Why is no real title available?)
• A polynomial time algorithm for diophantine equations in one variable
• A survey of computational complexity results in systems and control
• A variant of a recursively unsolvable problem
• Affine extensions of integer vector addition systems with states
• Computability with low-dimensional dynamical systems
• Context-free commutative grammars with integer counters and resets
• Decidability of membership problems for flat rational subsets of GL(2, Q) and singular matrices
• Deciding stability and mortality of piecewise affine dynamical systems
• Decision problems for semi-Thue systems with a few rules
• Improved matrix pair undecidability results
• Integer vector addition systems with states
• Iterated maps on the interval as dynamical systems
• Mortality of iterated piecewise affine functions over the integers: decidability and complexity
• Occurrence of zero in a linear recursive sequence
• On Affine Reachability Problems
• On the complexity of bounded time and precision reachability for piecewise affine systems
• On undecidability bounds for matrix decision problems
• Polynomial automata: zeroness and applications
• REACHABILITY PROBLEMS IN LOW-DIMENSIONAL ITERATIVE MAPS
• Reachability in register machines with polynomial updates
• Reachability problem for polynomial iteration is PSPACE-complete
• Reachability problems for PAMs
• Reachability problems for one-dimensional piecewise affine maps
• Reachability problems in nondeterministic polynomial maps on the integers
• Reducibility among combinatorial problems
• Remarks on blind and partially blind one-way multicounter machines
• The invariance problem for matrix semigroups
• The target discounted-sum problem
• Unboundedness problems for languages of vector addition systems
• Undecidability bounds for integer matrices using Claus instances
• Undecidability in binary tag systems and the Post correspondence problem for five pairs of words

Cited in

(7)

• Reachability problem for polynomial iteration is PSPACE-complete
• About the decision of reachability for register machines
• Reachability problems for one-dimensional piecewise affine maps
• REACHABILITY PROBLEMS IN LOW-DIMENSIONAL ITERATIVE MAPS
• 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
• 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)