Algorithms for the boundedness problem for Minsky counter machines
Egor V. Kuzmin, Dmitry Ju. Chalyy · Automatic Control and Computer Sciences · 2010
In this paper, algorithms that can be applied for solving the boundedness problem for Minsky counter machines are discussed. We introduce a polynomial-time algorithm that solves the boundedness problem for one-counter machines using memory commensurate with the memory required for the machine representation.