Geodesic
On the Efficient Representation of an Unbounded Resource with the Aid of~One-Counter Circuits
Modelirovanie i analiz informacionnyh sistem, Tome 20 (2013) no. 2, pp. 139-156

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

A class of infinite-state automata with a simple periodic behaviour and a convenient graphical representation is studied. A positive one-counter circuit is defined as a strongly connected one-counter net (one-counter nondeterministic finite automata without zero-testing) with at least one positive cycle. It is shown that in a positive circuit an infinite part of a reachability set is an arithmetic progression; numerical properties of this progression are estimated. A specific graphical representation of circuits is presented. General one-counter nets are equivalent to Petri Nets with at most one unbounded place and to pushdown automata with a single-symbol stack alphabet. It is shown that an arbitrary one-counter net can be represented by a finite tree of circuits. A one-counter net is called sound, if a counter is used only for “infinite-state” (periodic) behaviour. It is shown that for an arbitrary one-counter net an equivalent sound net can be effectively constructed from the corresponding tree of circuits.
Keywords: one-counter nets, Petri nets, reachability
Mots-clés : VASS, circuit. 
@article{MAIS_2013_20_2_a10,
     author = {V. A. Bashkin},
     title = {On the {Efficient} {Representation} of an {Unbounded} {Resource} with the {Aid} {of~One-Counter} {Circuits}},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {139--156},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2013_20_2_a10/}
}
TY  - JOUR
AU  - V. A. Bashkin
TI  - On the Efficient Representation of an Unbounded Resource with the Aid of~One-Counter Circuits
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2013
SP  - 139
EP  - 156
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2013_20_2_a10/
LA  - ru
ID  - MAIS_2013_20_2_a10
ER  - 
%0 Journal Article
%A V. A. Bashkin
%T On the Efficient Representation of an Unbounded Resource with the Aid of~One-Counter Circuits
%J Modelirovanie i analiz informacionnyh sistem
%D 2013
%P 139-156
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2013_20_2_a10/
%G ru
%F MAIS_2013_20_2_a10
V. A. Bashkin. On the Efficient Representation of an Unbounded Resource with the Aid of~One-Counter Circuits. Modelirovanie i analiz informacionnyh sistem, Tome 20 (2013) no. 2, pp. 139-156. http://geodesic.mathdoc.fr/item/MAIS_2013_20_2_a10/