Regularity and firing sequences of computation graphs

摘要

This paper studies in detail the order of firings, especially their recurrence properties, specified by computation graphs. The order of firings in a computation graph may be expressed by a change diagram which is, so to speak, a kind of non-labelled partially ordered graph. The regularity and ultimately dead edges are defined from the viewpoint of the order of firings. The ultimately dead edges are those which are ultimately redundant in specifying the order of firings. Briefly, a regular and only a regular strongly connected computation graph has the bounded queue property, except for redundant edges. A necessary and sufficient condition for a computation graph to be regular and an algorithm to decide the regularity are presented. Also a necessary and sufficient condition for a change diagram o be realized by a live marked graph is given.