Open AccessOn the Efficient Representation of an Unbounded Resource with the Aid of One-Counter Circuits
Author(s) -
Vladimir A. Bashkin
Publication year - 2015
Publication title -
modelirovanie i analiz informacionnyh sistem
Language(s) - English
Resource type - Journals
eISSN - 2313-5417
pISSN - 1818-1015
DOI - 10.18255/1818-1015-2013-2-139-156
Subject(s) - mathematics , petri net , nondeterministic algorithm , reachability , discrete mathematics , net (polyhedron) , electronic circuit , sequential logic , finite state machine , tree (set theory) , state (computer science) , computer science , arithmetic , algorithm , combinatorics , logic gate , geometry , electrical engineering , engineering
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.