Relations of flow languages to Petri net languages

AbstractA.C. Shaw has introduced the concept of the flow expression which is an extended regular expression and state several results with some conjectures. His conjecture that the flow expressions define context-sensitive languages has been answered negatively by two of the present authors, that is, the flow languages are recursively enumerable.In this paper, it is shown that flow languages for some restricted class of flow expressions are equivalent to Petri net languages. Some related decision problems for flow expressions are also discussed