Reachability problems in low-dimensional nondeterministic polynomial maps over integers
From MaRDI portal
Publication:2051802
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
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
- Affine extensions of integer vector addition systems with states
- 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
- Polynomial automata: zeroness and applications
- 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 (7)
- 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 problem for polynomial iteration is PSPACE-complete
- REACHABILITY PROBLEMS IN LOW-DIMENSIONAL ITERATIVE MAPS
- What else is undecidable about loops?
- Reachability problems for one-dimensional piecewise affine maps
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)
