1,721,290 research outputs found
SEPARABLE GRAPHS, PLANAR GRAPHS AND WEB GRAMMARS
No full textThis paper is concerned with the class of “web grammars,≓ introduced by Pfaltz and Rosenfeld, whose languages are sets of labelled graphs. A slightly modified definition of web grammar is given, in which the rewriting rules can have an applicability condition, and it is proved that, in general, this extension does not increase the generative power of the grammar. This extension is useful, however, for otherwise it is not possible to incorporate negative contextual conditions into the rules, since the context of a given vertex can be unbounded. A number of web grammars are presented which define interesting classes of graphs, including unseparable graphs, unseparable planar graphs and planar graphs. All the grammars in this paper use “normal embeddings≓ in which the connections between the web that is written and the host web are conserved, so that any rewriting rule affects the web only locally
ON THE IMPLEMENTATION OF CONCURRENT CALCULI IN NET CALCULI - 2 CASE-STUDIES
No full textConcurrent calculi, such as CCS, are defined in terms of labelled transition system; similarly, here we introduce the notion of net (or distributed) calculus, which is defined through a place/transition Petri net. As a first case study, a simple calculus of nets, called SCONE, is proposed, Relationships between SCONE and the subset of CCS without restriction and relabelling, called RCCS, are studied by showing that RCCS can be implemented in SCONE through a suitable mapping from the transition system for RCCS to net for SCONE. In particular, the complex CCS operation of global choice is implemented in terms of the SCONE finer grained operation of local choice, making explicit the fact that certain CCS transition are implemented as SCONE computations to be executed atomically. The result is a finite net implementation for RCCS agents. By making the quotient of the RCCS transition system w.r.t. the implementation mapping, we induce a truly concurrent semantics for RCCS. The second case study is then concerned with an extension dealing with restriction and relabelling. The resulting net calculus, called SCONE(+), is exploited as an implementation language for full CCS. The truly concurrent semantics induced by the implementation mapping is proved to coincide with the so-called ''permutation-of-transitions'' sematics
INTERNATIONAL JOINT CONFERENCE ON THEORY AND PRACTICE OF SOFTWARE-DEVELOPMENT, PISA, MARCH 1987
No full text- …
