RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Model. Anal. Inform. Sist.: Year: Volume: Issue: Page: Find

 Model. Anal. Inform. Sist., 2013, Volume 20, Number 2, Pages 139–156 (Mi mais304)

On the Efficient Representation of an Unbounded Resource with the Aid of One-Counter Circuits

V. A. Bashkin

P. G. Demidov Yaroslavl State University, Sovetskaya str., 14, Yaroslavl, 150000, Russia

Abstract: 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, VASS, Petri nets, reachability, circuit.

Full text: PDF file (519 kB)
References: PDF file   HTML file
UDC: 519.71+004.021

Citation: V. A. Bashkin, “On the Efficient Representation of an Unbounded Resource with the Aid of One-Counter 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~One-Counter Circuits \jour Model. Anal. Inform. Sist. \yr 2013 \vol 20 \issue 2 \pages 139--156 \mathnet{http://mi.mathnet.ru/mais304}