One-counter circuits

Concurrency, Specification and Programming

Vladimir A. Bashkin

Others  :  http://ceur-ws.org/Vol-928/0025.pdf
PID  :  27452

来源: CEUR

【 摘 要 】

One-counter nets are nondeterministic one-counter automatawithout zero-testing (Petri Nets with at most one unbounded place). A one-counter circuit of length ∆ is a strongly connected one-counter net, such that ∆ is a greatest common divisor of effects of all its cycles. A circuit has simple periodic behaviour: for any control state the set of corresponding reachable counter values is an arithmetic progression with difference ∆ (with an exception of a bounded subset). Properties of circuits and general one-counter nets are studied. It is shown that the infinite behaviour of a one-counter net can be represented by a composition of a finite set of circuits.