Categorical Approach to Horizontal Structuring and Refinement of High-Level Replacement Systems

Based on the well-known theory of high-level replacement systems – a categorical formulation of graph grammars – we present new results concerning refinement of high-level replacement systems. Motivated by Petri nets, where refinement is often given by morphisms, we give a categorical notion of refinement. This concept is called Q-transformations and is established within the framework of high-level replacement systems. The main idea is to supply rules with an additional morphism, which belongs to a specific class Q of morphisms. This leads to the new notions of Q-rules and Q-transformations. Moreover, several concepts and results of high-level replacement systems are extended to Q-transformations. These are sequential and parallel transformations, union, and fusion, based on different colimit constructions. The main results concern the compatibility of these constructions with Q-transformations that is the corresponding theorems for usual transformations are extended to Q-transformations. Finally, we demonstrate the application of these techniques for the special case of Petri nets to a case study concerning the requirements engineering of a medical information system.     

A left part theorem for grammatical trees

A simple left part property for a set of grammatical trees is introduced. The class of left part grammars, a subclass of the class of context-free grammars, is defined. It is shown that the set of grammatical trees of a context-free grammar satisfies this left part property if and only if the context-free grammar is a left part grammar. Some properties of leftpart grammars are considered.     

Quantum model of emerging grammars

A special class of quantum recurrent nets (QRNs) simulating Markov chains with absorbing states is introduced. The absorbing states are exploited for pattern recognition: each class of patterns is attracted to a unique absorbing state. Due to quantum interference of patterns, each combination of patterns acquires its own meaning: it is attracted to a certain combination of absorbing states which is different from those of individual attractions. This fundamentally new effect can be interpreted as formation of a grammar, i.e., a set of rules assigning certain meaning to different combinations of patterns. It appears that there exists a class of unitary operators in which each member gives rise to a different artificial language with associated grammar.     

A sentence generator for testing parsers

A fast algorithm is given to produce a small set of short sentences from a context free grammar such that each production of the grammar is used at least once. The sentences are useful for testing parsing programs and for debugging grammars (finding errors in a grammar which causes it to specify some language other than the one intended). Some experimental results from using the sentences to test some automatically generated simpleLR(1) parsers are also given.     

A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications

Coalitional games raise a number of important questions from the point of view of computer science, key among them being how to represent such games compactly, and how to efficiently compute solution concepts assuming such representations. Marginal contribution nets (MC‐nets), introduced by Ieong and Shoham, are one of the simplest and most influential representation schemes for coalitional games. MC‐nets are a rulebased formalism, in which rules take the form pattern → value, where “pattern ” is a Boolean condition over agents, and “value ” is a numeric value. Ieong and Shoham showed that, for a class of what we will call “basic” MC‐nets, where patterns are constrained to be a conjunction of literals, marginal contribution nets permit the easy computation of solution concepts such as the Shapley value. However, there are very natural classes of coalitional games that require an exponential number of such basic MC‐net rules. We present read‐once MC‐nets, a new class of MC‐nets that is provably more compact than basic MC‐nets, while retaining the attractive computational properties of basic MC‐nets. We show how the techniques we develop for read‐once MC‐nets can be applied to other domains, in particular, computing solution concepts in network flow games on series‐parallel networks (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Constrained regulation of continuous Petri nets

This paper deals with constrained regulation of continuous Petri nets under the so-called infinite servers semantics. Our aim is to design feedback gains that permit us to reach both desired stationary marking vector and desired asymptotic firing rate vector. The proposed approach takes into account constraints on the control, the marking of the Petri net, and the stability of the closed-loop system. The existence of a solution is first expressed geometrically, in terms of the inclusion of two polyhedral sets. They are reformulated algebraically as linear matrix inequalities, which provides an effective way to calculate feedback gains answering the problem. Finally, an application to an assembly production system is given.     

Categorical principles,techniques and results for high-level-replacement systems in computer science

The aim of this paper is to give an introduction how to use categorical methods in a specific field of computer science: The field of high-level-replacement systems has its roots in the well-established theories of formal languages, term rewriting, Petri nets, and graph grammars playing a fundamental role in computer science. More precisely, it is a generalization of the algebraic approach to graph grammars which is based on gluing constructions for graphs defined as pushouts in the category of graphs. The categorical theory of high-level-replacement systems is suitable for the dynamic handling of a large variety of high-level structures in computer science including different kinds of graphs and algebraic specifications. In this paper we discuss the basic principles and techniques from category theory applied in the field of high-level-replacement systems and present some basic results together with the corresponding categorical proof techniques.     

Fluid stochastic Petri nets: Theory,applications, and solution techniques

In this paper we introduce a new class of stochastic Petri nets in which one or more places can hold fluid rather than discrete tokens. We define a class of fluid stochastic Petri nets in such a way that the discrete and continuous portions may affect each other. Following this definition we provide equations for their transient and steady-state behavior. We present several examples showing the utility of the construct in communication network modeling and reliability analysis, and discuss important special cases. We then discuss numerical methods for computing the transient behavior of such nets. Finally, some numerical examples are presented and evidence of the accuracy of the fluid approximation is given.     

Nondeterministic dynamic programming on a parallel coprocessing system

We describe how nondeterministic dynamic programming (DP) algorithms can be designed for a new class of parallel coprocessing systems using “functional memory”, an architecture based upon dataflow computer principles. We also show how Petri nets can be used to model and express such parallel DP algorithms. Finally, we discuss architectural improvements that would facilitate the processing of Petri net models of nondeterministic DP algorithms on functional memory computers (FMC).     

From Petri Nets to Automata with Concurrency

Automata with concurrency relations are labelled transition systems with a collection of state-dependent binary independence relations for the actions. We show how to associate with each Petri net (place/transition net) such an automaton having the same dynamic behaviour. We characterize the automata arising in this way, and with suitable notions of morphisms for Petri nets and for automata with concurrency relations we extend this correspondence to a coreflection between the associated categories. As a consequence, we derive that these categories have products and conditional coproducts.     

A comprehensive approach of planning and scheduling based on petri nets

The main results available on the use of black-and-white Petri nets for modelling, planning and scheduling manufacturing systems are presented. In the first part of the paper, the basics of Petri nets necessary to understand the subsequent presentation are introduced. Particular attention is paid to event graphs, a particular type of Petri nets used for modelling and evaluating ratio-driven systems. The second part of the paper is devoted to ratio-driven systems, their modelling and their scheduling. Job-shops, assembly systems, and KANBAN systems are used to illustrate this section. Finally, the general case is investigated of manufacturing systems subject to changing demands. An approach based on conflict-free Petri nets with input and output transitions is proposed for planning and scheduling this type of system.     

Symmetries in timed continuous Petri nets

The dynamics of timed continuous Petri nets under infinite server semantics can be expressed in terms of a piecewise linear system with polyhedral regions. In this article, Petri nets with symmetries are considered where symmetry is understood as a permutation symmetry of the nodes. We establish connections between the qualitative dynamical behavior of the continuous marking and the symmetries. In particular, it is shown that such a symmetry leads to a permutation of the regions and to equivariant dynamics. This allows us to identify special flow-invariant sets which can be used for reductions to systems of smaller dimension. For general piecewise linear systems with polyhedral regions, it is shown that equivariant dynamics always implies a permutation of the regions.     

A note on one-pass evaluation of attribute grammars

An attribute grammar is considered to be one-pass if all the attribute instances of any derivation tree can be evaluated by a process that traverses the tree from left to right visiting each subtree at most once. It is shown that this general class of one-pass grammars properly includesL-attributed grammars; in fact,L-attributed grammars can be viewed as a practical subset of the general class. General one-pass grammars can be evaluated using recursive procedures in the same way as forL-attributed grammars, provided that call-by-name parameters are available.     

Grammar functors and covers: From non-left-recursive to greibach normal form grammars

Attention is paid to structure preserving properties of transformations from a non-left-recursive context-free grammar to a Greibach normal form grammar. It is demonstrated that such a transformation cannot only be ambiguity preserving, but also both cover and functor relations between grammars or their associated syntax-categories can be obtained from such a transformation.     

Duality theory and propagation rules for higher order nets

Higher order nets and sequences are used in quasi-Monte Carlo rules for the approximation of high dimensional integrals over the unit cube. Hence one wants to have higher order nets and sequences of high quality.In this paper we introduce a duality theory for higher order nets whose construction is not necessarily based on linear algebra over finite fields. We use this duality theory to prove propagation rules for such nets. This way we can obtain new higher order nets (sometimes with improved quality) from existing ones. We also extend our approach to the construction of higher order sequences.     

A polynomial time algorithm for finding the prime factors of cartesian-product graphs

We consider the computational complexity of recognizinf concerned cartesian product graphs. Sabidussi gives a non-algorithmic proof that the cartesian factorization is unique. He uses a tower of successively coarser equivalence relations on the edge set in which each prime factor of the graph is identified with an equivalence class in the coarsest of the relations. We first explore the structure and size of the relation at the base of the tower. Then we give a polynomial-time algorithm to compute the relations and to construct the prime factors of any connected graph. The bounds on the size of the relations are crucial to the runtime analysis of our algorithm.     

Orthomorphism graphs of groups

We introduce the concept of the orthomorphism graph of a group. An r-clique of the orthomorphism graph of a group G corresponds to a set of r+1 mutually orthogonal latin squares based on the group G. In this paper we give constructions of nets, affine planes and cartesian groups using cliques of orthomorphism graphs and we discuss the relationship between properties of the cliques and properties of the nets constructed.     

A Petri net approach to the modelling and analysis of flexible manufacturing systems

In this paper we present an approach for modelling and analyzing flexible manufacturing systems (FMSs) using Petri nets. In this approach, we first build a Petri net model (PNM) of the given FMS in a bottom-up fashion and then analyze important qualitative aspects of FMS behaviour such as existence/absence of deadlocks and buffer overflows. The basis for our approach is a theorem we state and prove for computing the invariants of the union of a finite number of Petri nets when the invariants of the individual nets are known. We illustrate our approach using two typical manufacturing systems: an automated transfer line and a simple FMS.A shorter version of this paper was presented at the 1st ORSA/TIMS Special Interest Conference on FMSs, University of Michigan, Ann Arbor, August 1984.     

On Commutative and Nonassociative Syntactic Calculi and Categorial Grammars

Two axiomatizations of the nonassociative and commutative Lambek syntactic calculus are given and their equivalence is proved. The first axiomatization employs Permutation as the only structural rule, the second one, with no Permutation rule, employs only unidirectional types. It is also shown that in the case of the Ajdukiewicz calculus an analogous equivalence is valid only in the case of a restricted set of formulas. Unidirectional axiomatizations are employed in order to establish the generative power of categorial grammars based on the nonassociative and commutative Lambek calculus with product. Those grammars produce CF-languages of finite degree generated by CF-grammars closed with respect to permutations.