Approximating Bisimulation in One-counter Nets - V. A. Bashkin (Моделирование и анализ информационных систем, 2011)
One-counter nets are finite-state machines operating on a variable (counter) which ranges over the natural numbers. Every transition can increase or decrease the value of the counter (the decrease is possible only if the result is non-negative, hence zero-testing is not allowed). The class of one-counter nets is equivalent to the class of Petri nets with one unbounded place, and to the class of pushdown automata where the stack alphabet contains one symbol. We present a specific method of approximation of the largest bisimulation of a one-counter net, based on the single-periodic arithmetics and a notion of stratified bisimulation.