Geodesic
The boundedness problem for lossy counter machines
Modelirovanie i analiz informacionnyh sistem, Tome 15 (2008) no. 3, pp. 14-27 
E. V. Kuz'min. The boundedness problem for lossy counter machines. Modelirovanie i analiz informacionnyh sistem, Tome 15 (2008) no. 3, pp. 14-27. http://geodesic.mathdoc.fr/item/MAIS_2008_15_3_a1/
@article{MAIS_2008_15_3_a1,
     author = {E. V. Kuz'min},
     title = {The boundedness problem for lossy counter machines},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {14--27},
     year = {2008},
     volume = {15},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2008_15_3_a1/}
}
TY  - JOUR
AU  - E. V. Kuz'min
TI  - The boundedness problem for lossy counter machines
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2008
SP  - 14
EP  - 27
VL  - 15
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/MAIS_2008_15_3_a1/
LA  - ru
ID  - MAIS_2008_15_3_a1
ER  - 
%0 Journal Article
%A E. V. Kuz'min
%T The boundedness problem for lossy counter machines
%J Modelirovanie i analiz informacionnyh sistem
%D 2008
%P 14-27
%V 15
%N 3
%U http://geodesic.mathdoc.fr/item/MAIS_2008_15_3_a1/
%G ru
%F MAIS_2008_15_3_a1

Voir la notice de l'article provenant de la source Math-Net.Ru

In the paper the decidability of the boundedness problem for lossy counter Minsky machines is investigated. It is proved, that for Minsky machines with three counters the boundedness is not decidable for any lossiness relation on the set of machine configurations. It is introduced the notion of reset one-register machines, which can simulate two-counter machines with the reset lossiness relation. It is proved, that the boundedness is decidable for reset one-register machines (and, hence, for reset two-counter machines).

[1] E. M. Klark, O. Gramberg, D. Peled, Verifikatsiya modelei programm: Model Checking, MTsNMO, 2002, 416 pp.

[2] E. V. Kuzmin, V. A. Sokolov, Strukturirovannye sistemy perekhodov, FIZMATLIT, M., 2006, 178 pp. | MR

[3] E. V. Kuzmin, D. Yu. Chalyi, “O razreshimosti problem ogranichennosti dlya schetchikovykh mashin Minskogo”, Modelirovanie i analiz informatsionnykh sistem, 15:1 (2008), 16–26

[4] M. Minskii, Vychisleniya i avtomaty, Mir, M., 1971, 268 pp. | MR

[5] C. Dufourd, P. Jancar, Ph. Schnoebelen, “Boundedness of Reset P/T nets”, Proc. ICALP'99, LNCS, 1644, 1999, 301–310 | MR | Zbl

[6] R. Mayr, Lossy counter machines, Tech. Report TUM-I9827, Institut für Informatik, TUM, Germany, October 1998

[7] R. Schroeppel, A Two counter Machine Cannot Calculate $2^N$, Artificial Intelligence Memo #257, Massachusetts Institute of Technology, A.I. Laboratory, 1972, 32 pp.