Geodesic
On a class of counter machines
Modelirovanie i analiz informacionnyh sistem, Tome 16 (2009) no. 2, pp. 75-82.

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

In this paper we propose abstract counter machines as a general framework for analysing state systems with counters. We use this framework to define weak counter machines and a new class of counter machines — automaton counter machines which can be modeled by Communicating Coloured Automata (introduced in [11]). Particular emphasis has been placed on comparing automaton counter machines with weak counter machines which can be modeled by Petri nets. We show undecidability of boundedness, inclusion, equivalence and a special case of reachability for automaton counter machines. This implies that the same holds for Communicating Colouring Automata.
Keywords: abstract counter machines, automaton counter machine, Communicating Colouring Automata, verification, decidability. 
@article{MAIS_2009_16_2_a2,
     author = {E. V. Kuzmin and D. Yu. Chalyy},
     title = {On a class of counter machines},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {75--82},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2009_16_2_a2/}
}
TY  - JOUR
AU  - E. V. Kuzmin
AU  - D. Yu. Chalyy
TI  - On a class of counter machines
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2009
SP  - 75
EP  - 82
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2009_16_2_a2/
LA  - ru
ID  - MAIS_2009_16_2_a2
ER  - 
%0 Journal Article
%A E. V. Kuzmin
%A D. Yu. Chalyy
%T On a class of counter machines
%J Modelirovanie i analiz informacionnyh sistem
%D 2009
%P 75-82
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2009_16_2_a2/
%G ru
%F MAIS_2009_16_2_a2
E. V. Kuzmin; D. Yu. Chalyy. On a class of counter machines. Modelirovanie i analiz informacionnyh sistem, Tome 16 (2009) no. 2, pp. 75-82. http://geodesic.mathdoc.fr/item/MAIS_2009_16_2_a2/

[1] P. A. Abdulla, K. Čerāns, B. Jonsson, T. Yih-Kuen, General decidability theorems for infinite-state systems, Proc. 11th IEEE Symp. Logic in Computer Science (LICS'96), 1996, 313–321 | MR

[2] T. Araki, T. Kasami, “Some Decision Problems Related to the Reachability Problem for Petri Nets”, Theoretical Computer Science, 3 (1977), 85–104 | DOI | MR | Zbl

[3] L. E. Dickson, “Finiteness of the odd perfect and primitive abundant numbers with $r$ distinct prime factors”, Amer. Journal Math., 35 (1913), 413–422 | DOI | MR | Zbl

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

[5] A. Finkel, Ph. Schnoebelen, “Well-structured transition systems everywhere!”, Theoretical Computer Science, 256:1-2 (2001), 63–92 | DOI | MR | Zbl

[6] A. Finkel,G. Sutre, “ An Algorithm Constructing the Semilinear Post* for 2-Dim Reset/Transfer VASS”, MFCS 2000, LNCS, 1893, Springer, 2000, 353–362 | MR | Zbl

[7] A. Finkel, G. Sutre, “ Decidability of Reachability Problems for Classes of Two-Counter Automata”, STACS 2000, LNCS, 1770, Springer, 2000, 346–357 | MR | Zbl

[8] M. Hack M., Decision problems for Petri nets and vector addition systems, Project MAC Memo 59, Cambridge, 1975

[9] Hack M., “The equality problem for vector addition systems is undecidable”, Theoretical Computer Science, 2:1 (1976), 77–96 | DOI | MR

[10] J. E. Hopcroft, J. Pansiot, On the Reachability Problem for 5-Dimensional Vector Addition Systems., Computer science technical report, Cornell University, 1976 http://hdl.handle.net/1813/6102

[11] E. V. Kouzmin, V. A.Sokolov, Communicating Colouring Automata, Proc. Int. Workshop on Program Understanding (sat. of PSI'03), 2003, 40–46

[12] E. V. Kouzmin, N. V. Shilov, V. A. Sokolov, Model Checking $\mu$-Calculus in Well-Structured Transition Systems, Proc. 11th Int. Symposium on Temporal Representation and Reasoning, IEEE Press, Tatihou, France, 2004, 152–155

[13] E. V. Kouzmin, N. V. Shilov, V. A. Sokolov, “Model Checking $\mu$-Calculus in Well-Structured Transition Systems”, Joint Bulletin of NCC IIS, Comp. Science, 20, Novosibirsk, 2004, 49–59 | Zbl

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

[15] E. V. Kuzmin, “Nedeterminirovannye schetchikovye mashiny”, Modelirovanie i analiz informatsionnykh sistem, 10:2 (2003), 41–49 | MR

[16] E. V. Kuzmin, V. A. Sokolov, “Vzaimodeistvuyuschie raskrashivayuschie protsessy”, Modelirovanie i analiz informatsionnykh sistem, 11:2 (2004), 8–17

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

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

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