Algorithms for the boundedness problem for Minsky counter machines

E. V. Kuzmin, D. Ju. Chalyy

Yaroslavl State University

Abstract: In the paper, the algorithms that can be applied to solving the boundedness problem for Minsky counter machines are discussed. We introduce a polinomial-time algorithm that solves the boundedness problem for one-counter machines using the memory commensurate with the memory required for a machine representation.

Keywords: Minsky counter machines, boundedness problem, algorithm of the search of a cycle in a periodic sequence, model verification.

UDC: 519.7

Received: 02.11.2008