Monday, September 03, 2007

Reducibility Between Classes of Port Graph Grammar

... by Charles Stewart (a.k.a. cas).

It is interesting to compare reducability results for PGGs with those for JCs (especially general SPGG in basic SPGG to general JC in core JC).

As a side note, I start to become uneasy with too complicated encodings... There should be some more fine-grained equivalence than an ability to encode one transformation system in another (something along the lines of expressivity).

For example, the standard encoding of general JC in core JC is not homomorphic in constructs of core JC - implying it is not identity on core JC terms - so this encoding does not prove expressibility of general JC in core JC Felleisen-wise.

PS: linearity.org seems to be down for some reason.

1 comment:

Andris Birkmanis said...

It turned out that reducability defined by Charles Stewart is more of internal notion, while one used by Felleisen differentiates terms based on external observations (whether or not termination of the terms always coincides in any context).