HP Labs Technical Reports

Concurrent Counter Automata

Kotov, Vadim



Abstract: The report proposes and studies an automata model of concurrent processes. A concurrent counter automaton over a set of actions is a finite set of statements, each of which consists of an action symbol and a guard. The guard is a set of arithmetic expressions over counters whose names coincide with the action symbols. A current value of counter is the number of previous occurrences of the corresponding action. Initially, all counters are set to 0. When tested, the guard returns a set of non-negative numbers. If all the numbers are greater then the current number of occurrences of the statement action, then the statement's value becomes true and the correspondent action may occur and increment the value of the associated counter by 1. The automaton stops if none of its statements may become true. The relationship between concurrent counter automata and Petri nets is established. A class of compositional counter automata is introduced by defining operations over automata. Possible extensions of the basic interleaving version of automata are discussed. These extensions lead toward true concurrent and hierarchical models as well as toward models augmented by additional information about actions, states and history of computation. Concurrent counter automata may be viewed as a concretization of a geometrical modeling of concurrency advocated by V. Pratt.

Back to Index

[Research] [News] [Tech Reports] [Palo Alto] [Bristol] [Japan] [Israel] [Site Map] [Home] [Hewlett-Packard]