Parsing Partially Ordered Multisets
A partially ordered multiset or pomset is a generalization of a string
in which the total order has been relaxed to a partial order. Strings
are often used as a model for sequential computation; pomsets are a
natural model for parallel and distributed computation.
By viewing pomsets as a generalization of strings, the question is
raised whether concepts from language theory can be generalized to
pomsets. An important area in the theory of languages is parsing theory.
This paper develops the fundamentals of a parsing theory for pomsets,
called PLR parsing. It is based on the LR-parsing
technique, which is the most powerful deterministic parsing technique
in language theory. The basic algorithm in the class of PLR
parsing algorithms, the PLR(0) algorithm is explained in
detail.
(postscript /
pdf version of the complete paper)
Back to the list of publications.