On the Efficient Representation of an Unbounded Resource with the Aid of One-Counter Circuits
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 c...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2013-04-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/212 |
| _version_ | 1797877962033332224 |
|---|---|
| author | V. A. Bashkin |
| author_facet | V. A. Bashkin |
| author_sort | V. A. Bashkin |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-10T02:25:08Z |
| format | Article |
| id | doaj.art-9ab081ced6d74e60bf2941d634ee61c0 |
| institution | Directory Open Access Journal |
| issn | 1818-1015 2313-5417 |
| language | English |
| last_indexed | 2024-04-10T02:25:08Z |
| publishDate | 2013-04-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj.art-9ab081ced6d74e60bf2941d634ee61c02023-03-13T08:07:31ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172013-04-0120213915610.18255/1818-1015-2013-2-139-156206On the Efficient Representation of an Unbounded Resource with the Aid of One-Counter CircuitsV. A. Bashkin0Ярославский государственный университет им. П. Г. Демидова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.https://www.mais-journal.ru/jour/article/view/212односчетчиковые сетиvassсети петридостижимостьконтур |
| spellingShingle | V. A. Bashkin On the Efficient Representation of an Unbounded Resource with the Aid of One-Counter Circuits Моделирование и анализ информационных систем односчетчиковые сети vass сети петри достижимость контур |
| title | On the Efficient Representation of an Unbounded Resource with the Aid of One-Counter Circuits |
| title_full | On the Efficient Representation of an Unbounded Resource with the Aid of One-Counter Circuits |
| title_fullStr | On the Efficient Representation of an Unbounded Resource with the Aid of One-Counter Circuits |
| title_full_unstemmed | On the Efficient Representation of an Unbounded Resource with the Aid of One-Counter Circuits |
| title_short | On the Efficient Representation of an Unbounded Resource with the Aid of One-Counter Circuits |
| title_sort | on the efficient representation of an unbounded resource with the aid of one counter circuits |
| topic | односчетчиковые сети vass сети петри достижимость контур |
| url | https://www.mais-journal.ru/jour/article/view/212 |
| work_keys_str_mv | AT vabashkin ontheefficientrepresentationofanunboundedresourcewiththeaidofonecountercircuits |