Geodesic
On the decidability of boundedness problems for counter Minsky machines
Modelirovanie i analiz informacionnyh sistem, Tome 15 (2008) no. 1, pp. 16-26.

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

In the paper the decidability of boundedness problems for counter Minsky machines is investigated. It is proved, that for Minsky machines with two counters the boundedness is partial decidable, but for the total boundedness problem does not even exist a semidecision algorithm. On the other hand, for one-counter Minsky machines all these problems are polinomial (quantitatively of local machine states) decidable. 
@article{MAIS_2008_15_1_a2,
     author = {E. V. Kuzmin and D. Ju. Chalyy},
     title = {On the decidability of boundedness problems for counter {Minsky} machines},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {16--26},
     publisher = {mathdoc},
     volume = {15},
     number = {1},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2008_15_1_a2/}
}
TY  - JOUR
AU  - E. V. Kuzmin
AU  - D. Ju. Chalyy
TI  - On the decidability of boundedness problems for counter Minsky machines
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2008
SP  - 16
EP  - 26
VL  - 15
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2008_15_1_a2/
LA  - ru
ID  - MAIS_2008_15_1_a2
ER  - 
%0 Journal Article
%A E. V. Kuzmin
%A D. Ju. Chalyy
%T On the decidability of boundedness problems for counter Minsky machines
%J Modelirovanie i analiz informacionnyh sistem
%D 2008
%P 16-26
%V 15
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2008_15_1_a2/
%G ru
%F MAIS_2008_15_1_a2
E. V. Kuzmin; D. Ju. Chalyy. On the decidability of boundedness problems for counter Minsky machines. Modelirovanie i analiz informacionnyh sistem, Tome 15 (2008) no. 1, pp. 16-26. http://geodesic.mathdoc.fr/item/MAIS_2008_15_1_a2/

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

[2] V. E. Kotov, Seti Petri, Nauka, M., 1984, 160 pp. | MR

[3] V. E. Kotov, V. K. Sabelfeld, Teoriya skhem programm, Nauka, M., 1991, 248 pp. | MR

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

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

[6] D. Khopkroft, R. Motvani, D. Ulman, Vvedenie v teoriyu avtomatov, yazykov i vychislenii, 2-e izd., Vilyams, M., 2002, 528 pp.

[7] C. Chitic, D. Rosu, “On validation of XML streams using finite state machines”, WebDB, Paris, 2004, 85–90

[8] S. Demri, R. Lazic, A. Sangnier, “Model checking freeze LTL over one-counter automata”, Proceedings of the 11th International Conference on Foundations of Software, Science and Computation Structures (FoSSaCS'08), LNCS, 2008 http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/DLS-fossacs08.pdf | MR

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

[10] P. Lafourcade, D. Lugiez, R. Treinen, “Intruder deduction for AC-like equational theories with homomorphisms”, RTA'05, LNCS, 3467, Springer, 2005, 308–322 | MR | Zbl

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

[12] M. Wakatsuki, K. Teraguchi, E. Tomita, “Polynomial time identification of strict deterministic restricted one-counter automata in some class from positive data”, ICGI 2004, Athens, LNAI, 3264, Springer, 2004, 260–272 | Zbl