Author name cluster

H.C.M. Kleijn

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

1 author row

I&C Journal 2004 Journal Article

Process semantics of general inhibitor nets

H.C.M. Kleijn
M. Koutny

We define a causality semantics of Place/Transition nets with weighted inhibitor arcs (PTI-nets). We extend the standard approach to defining the partial order semantics of Place/Transition nets (PT-nets) based on the process semantics given through occurrence nets. To deal with inhibitor arcs at the level of occurrence nets activator arcs (and extra conditions) are used. The properties of the resulting activator occurrence nets are extensively investigated. It is then demonstrated how processes corresponding to step sequences of PTI-nets can be constructed algorithmically, and a non-algorithmic (axiomatic) characterisation is given of all those processes that can be obtained in this way. In addition, a general framework is established allowing to separately discuss behaviour, processes, causality, and their properties before proving that the resulting notions are mutually consistent for the various classes of Petri nets considered. This facilitates an efficient and uniform presentation of our results.

Details DOI

TCS Journal 1997 Journal Article

Restrictions and representations of vector controlled concurrent system behaviours

N.W. Keesmaat
H.C.M. Kleijn

Within the framework of Vector Controlled Concurrent Systems a concurrent system consists of a fixed number of sequential processes together with a vector synchronization mechanism controlling their mutual synchronization. The behaviour of a VCCS is described by a vector language consisting of those combinations of individual sequential computations that observe the synchronization constraints. In this paper VCCS submodels are studied that are obtained by putting certain restrictions on the sequential components or on the control mechanism. First, the inclusion diagram relating the resulting families of vector languages is established. Next, the effect of certain operations on these families is investigated. This leads to representation results characterizing differences between the combinations of restrictions.

Details DOI

TCS Journal 1996 Journal Article

An event structure semantics for general Petri nets

P.W. Hoogers
H.C.M. Kleijn
P.S. Thiagarajan

In this paper we address the following question: What type of event structures are suitable for representing the behaviour of general Petri nets? As a partial answer to this question we define a new class of event structures called local event structures and identify a subclass called UL-event structures. We propose that UL-event structures are appropriate for capturing the behaviour of general Petri nets. Our answer is a partial one in that in the proposed event structure semantics, auto-concurrency is filtered out from the behaviour of Petri nets. It turns out that this limited event structure semantics for Petri nets is nevertheless a non-trivial and conservative extension of the (prime) event structure semantics of 1-safe Petri nets provided in Nielsen et al. (1981). We also show that the strong relationship between prime event structures and 1-safe Petri nets established in a categorical framework in Winskel (1987) can be extended to the present setting, provided we restrict our attention to the subclass of Petri nets whose behaviours do not exhibit any auto-concurrency. Finally, we show that Winskel's general and stable event structures can be smoothly related to local event structures and that similarly prime event structures can be related to UL-event structures.

Details DOI

I&C Journal 1995 Journal Article

A Trace Semantics for Petri Nets

P.W. Hoogers
H.C.M. Kleijn
P.S. Thiagarajan

A generalization of the notion of trace is proposed. This enables us to associate with each Petri net a single behavioural object, namely a poset of (generalized) traces. A characterization is given of the trace languages defined by Petri nets. We show that the general event structures of Winskel and the stable event structures can also be characterized in terms of our trace languages. One consequence is that in this framework, stable event structures, general event structures, and Petri nets constitute a strictly ascending chain in terms of expressive power.

Details DOI

TCS Journal 1994 Journal Article

Representation of rational functions with prefix and suffix codings

T. Harju
H.C.M. Kleijn
M. Latteux
A. Terlutte

We proceed with the characterization of rational functions by means of restricted class of morphisms. Left subsequential transductions can be factored in an endmarking followed by an uniform morphism, the inverse of a prefix morphism and an alphabetic morphism. Rational functions require the inverse of a prefix morphism followed by the inverse of a suffix morphism.

Details DOI

TCS Journal 1985 Journal Article

Adding global forbidding context to context-free grammars

A. Ehrenfeucht
H.C.M. Kleijn
G. Rozenberg

A 1S grammar generalizes a context-free grammar in the following way: a production A → α can be applied to a string uAv (to rewrite the designed occurence of A) provided that all letters from u belong to a fixed alphabet X and all letters from v belong to a fixed alphabet Z (the alphabets X and Z are independent of the production). It is proved that a language is generated by a 1S grammar if and only if it is context-free: this solves an open problem from the theory of selective substitution grammars (Kleijn and Rozenberg, 1981/82).

Details DOI

TCS Journal 1981 Journal Article

Context-free like restrictions on selective rewriting

H.C.M. Kleijn
G. Rozenberg

Selective substitution grammars based on ‘context-free’ productions form a possible framework for the study of ‘grammatically oriented’ formal language theory. Such grammars (with no control governing the composition of derivation steps) are studied in this paper. In particular we study the effect of various conditions on selectors (which define the way that rewriting is performed); those conditions are aimed to formalize the notion of ‘using information about the context’ during the rewriting process. Each of them captures a particular feature of a rewriting according to a context-free grammar or an EOS system (essentially a context-free grammar that can also rewrite terminal symbols). Some of those conditions yield characterizations of the class of context-free languages for other conditions the lower and upper bound on the language generating power are given. Also a natural notion of a class of ‘simple’ rewriting systems is introduced (pattern grammars) and it is demonstrated that they possess surprisingly high language generating power.

Details DOI