
On the Efficient Representation of an Unbounded Resource with the Aid of OneCounter Circuits
V. A. Bashkin^{} ^{} P. G. Demidov Yaroslavl State University, Sovetskaya str., 14, Yaroslavl, 150000, Russia
Abstract:
A class of infinitestate automata with a simple periodic behaviour and a convenient graphical representation is studied. A positive onecounter circuit is defined as a strongly connected onecounter net (onecounter nondeterministic finite automata without zerotesting) 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 onecounter nets are equivalent to Petri Nets with at most one unbounded place and to pushdown automata with a singlesymbol stack alphabet. It is shown that an arbitrary onecounter net can be represented by a finite tree of circuits. A onecounter net is called sound, if a counter is used only for “infinitestate” (periodic) behaviour. It is shown that for an arbitrary onecounter net an equivalent sound net can be effectively constructed from the corresponding tree of circuits.
Keywords:
onecounter nets, VASS, Petri nets, reachability, circuit.
Full text:
PDF file (519 kB)
References:
PDF file
HTML file
UDC:
519.71+004.021 Received: 20.03.2013
Citation:
V. A. Bashkin, “On the Efficient Representation of an Unbounded Resource with the Aid of OneCounter Circuits”, Model. Anal. Inform. Sist., 20:2 (2013), 139–156
Citation in format AMSBIB
\Bibitem{Bas13}
\by V.~A.~Bashkin
\paper On the Efficient Representation of an Unbounded Resource with the Aid of~OneCounter Circuits
\jour Model. Anal. Inform. Sist.
\yr 2013
\vol 20
\issue 2
\pages 139156
\mathnet{http://mi.mathnet.ru/mais304}
Linking options:
http://mi.mathnet.ru/eng/mais304 http://mi.mathnet.ru/eng/mais/v20/i2/p139
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles

Number of views: 
This page:  149  Full text:  57  References:  41 
