Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456

Address: [go: Go Back, main page]
Remove Scripts Accept Cookies Show Images Show Referer Rotate13 Base64 Strip Meta Strip Title Session Cookies

Failing to Give Proper Credit: Whence Pomsets?

27 February 2004

In the note Some of My Favourite Results in Classic Process Algebra, I have listed some of the many results I like in process algebra, broadly construed. One of them is a theorem of Steven Tschantz showing that the equational theory of languages over concatenation and shuffle coincides with that of series-parallel pomsets. In his proof, Tschantz essentially rediscovered the concept of pomset (a model of concurrency based on partial orders whose algebraic aspects have been investigated by Gischer).

In that note of mine, I attributed the concept of pomset to Vaughan Pratt, who made pomsets popular in much of the concurrency community with his work on those structures. Historically, however, as pointed out to me by Walter Vogler, pomsets had already been studied before Pratt took an interest in them. Walter wrote to me:

As so many, you quote Pratt for pomsets; these were already studied by Grabowski under the name of partial words in the journal article
J. Grabowski: On partial languages. Fundamenta Informaticae 4(2): 428-498 (1981)
Also in this paper, elements are events, partial words describe concurrent runs - in particular in connection with Petri nets; and as far as I remember, the paper also takes a 'formal language' perspective.

Since I am interested in the historic developments of our science, and in giving the proper credit to people, I find it appropriate to use this posting to set the record straight on the origins of the concept of pomsets. I have no excuse for omitting to cite Grabowski's work as I am aware of it. One should give proper credit where it is due, and I was lazy on that occasion.

A lesson one can learn from this story, and similar ones, is that it often happens that it is not the first discoverer of a notion who gets the credit for it, but rather the person who puts the concept on the scientific map for good. As I once read somewhere, Columbus did not become famous for being the first to discover America, but rather for being the last to do so! After he discovered that continent, America stayed "discovered", rather than slumber into oblivion. The same seems to happen for scientific discoveries/notions.