אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

One-Counter Nets (OCNs) are finite-state automata equipped with a counter that is not allowed to become negative, but cannot be tested for zero. The counter can naturally be viewed as a resource that is accumulated and consumed along a run. Motivated by branching extensions of Vector Addition Systems, we introduce and study Alternating One-Counter Nets (AOCNs), in which a universal transition distributes the available counter among several continuations, all of which are required to accept.

When several branches later reach the same state, there are different natural ways to interpret their counter values. We study two such semantics: in the SUM semantics the arriving resources are aggregated, whereas in the MIN semantics only the smallest counter value is retained. The latter captures the intuition that the different universal branches must each be able to survive independently.

We study the basic language-theoretic and algorithmic properties of AOCNs under these semantics. We show that both semantics are closed under union and intersection but not under complementation, and establish decidability results for the emptiness and universality problems. Finally, we investigate the relative expressive power of the SUM and MIN semantics. While their precise relationship remains open, we present examples and partial results that illustrate the substantially different behavior of the two semantics and the difficulties involved in separating them.