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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
Received: 20.03.2013

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}


Linking options:
  • http://mi.mathnet.ru/eng/mais304
  • http://mi.mathnet.ru/eng/mais/v20/i2/p139

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Моделирование и анализ информационных систем
    Number of views:
    This page:128
    Full text:37
    References:34

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019