On Partial Languages

Article type: Research Article

Authors: Grabowski, Jan

Affiliations: Humboldt University

Abstract: The paper studies the behavior of control structures of algorithms designed for (partly) parallel execution. A generalization of Peterson’s computation sequence set, the partial language, is discussed, which reflects the concurrency of events. In particular, the families of partial languages definable by Petri nets and by safe Petri nets are investigated with respect to closedness under certain operations. Trace languages (Mazurkiewicz) and path expressions (Campbell and Habermann) are included in the considerations.

Keywords: Computation sequence set, partial word, partial language, concurrent processes, Petri net, path expression, trace language

DOI: 10.3233/FI-1981-4210

Journal: Fundamenta Informaticae, vol. 4, no. 2, pp. 427-498, 1981