We investigate gcf-Petri nets, a generalization of communication-free Petri nets allowing arbitrary arc multiplicities, and characterized by the sole restriction that each transition has at most one incoming arc. We use canonical firing sequences with nice properties for gcf-PNs to show that the Re cLFS, (zero-)reachability, covering, and boundedness problems of gcf-PNs are in PSPACE. By simulating PSPACE-Turing machines by gss-PNs, a subclass of gcf-PNs where additionally all transitions have at most one outgoing arc, we ultimately obtain PSPACE-completess for these problems in case of gss-PNs or gcf-PNs. Additionally, we prove PSPACE-completeness for the liveness problem of gcf-PNs. Last, we show PSPACE-hardness as well as a doubly exponential space upper bound for the containment and equivalence problems of gss-PNs or gcf-PNs.

Front Matter, Table of Contents, Preface, Conference Organization

We investigate several computational problems of communication-free Petri nets, and develop very efficient (mostly linear time) algorithms for different variations of the boundedness and liveness problems of cf-PNs. For several more complex notions of boundedness, as well as for the covering problem, we show NP-completeness. In the last part, we use our results for cf-PNs to give linear time algorithms for related problems of context-free (commutative) grammars, and, in turn, use known results for such grammars to give a coNEXPTIME-upper bound for the equivalence problem of cf-PNs.

The computation of a Gröbner basis of a polynomial ideal is known to be exponential space complete. We revisit the algorithm by Kühnle and Mayr using recent improvements of various degree bounds. The result is an algorithm which is exponential in the ideal dimension (rather than the number of indeterminates).

Let K[X] be a ring of multivariate polynomials with coefficients in a field K, and let f1, ..., fs be polynomials with maximal total degree d which generate an ideal I of dimension r. Then, for every admissible ordering, the total degree of polynomials in a Grobner basis for I is bounded by 2 (1/2dn-r + d)2r. This is proved using the cone decompositions introduced by Dube in [5]. Also, a lower bound of similar form is given.

Embeddings of various graph classes into hypercubes have been widely studied. Almost all these classes are regularly structured graphs such as meshes, complete trees or pyramids. In this paper, we present a general method for one-to-one embeddings of irregularly structured graphs into their optimal hypercubes, based on extended edge bisectors of graphs. An extended edge bisector is an edge bisector with the additional property that a certain subset of the vertices is distributed more or less evenly among the two halves of the bisected graph. The dilation and congestion of our embedding depends on the quality of the extended edge bisector. Moreover, if the extended bisection can be computed efficiently on the hypercube, then so can the embedding. Our embedding technique can also be applied to embeddings into hypercube-like topologies such as folded hypercubes, twisted cubes, crossed cubes, Möbius cubes, Fibonacci cubes or star graphs.

) Petra Berenbrink Department of Mathematics and Computer Science Paderborn University, Germany Email: [email protected] Tom Friedetzky and Ernst W. Mayr y Institut fur Informatik Technische Universitat Munchen, Germany Email: (friedetz---mayr)@informatik.tu-muenchen.de Abstract Recently, the subject of allocating tasks to servers has attracted much attention. There are several ways of distinguishing load balancing problems. There are sequential and parallel strategies, that is, placing the tasks one after the other or all of them in parallel. Another approach divides load balancing problems into continuous and static ones. In the continuous case new tasks are generated and consumed as time proceeds, in the second case the number of tasks is fixed. We present and analyze a parallel randomized continuous load balancing algorithm in a scenario where n processors continuously generate and consume tasks according to some given probability distribution. Each processor initiates l...

In this paper, we present an optimal, exponential space algorithm for generating the reduced Grobner basis of binomial ideals.We make use of the close relationship between commutative semigroups and pure difference binomial ideals.Based on the algorithm for the uniform word problem in commutative semigroups exhibited by Mayr and Meyer we first derive an exponential space algorithm for constructing the reduced Grobner basis of a pure difference binomial ideal.In addition to some applications to finitely presented commutative semigroups, this algorithm is then extended to an exponential space algorithm for generating the reduced Grobner basis of binomial ideals over Q in general.

Given a polynomial ideal and a term order, there is a unique reduced Gröbner basis and, for each polynomial, a unique normal form, namely the smallest (w.r.t. the term order) polynomial in the same coset. We consider the problem of finding this normal form for any given polynomial, without prior computation of the Gröbner basis. This is done by transforming a representation of the normal form into a system of linear equations and solving this system. Using the ability to find normal forms, we show how to obtain the Grobner basis in exponential space.

Abstract We consider a new class of routing requests, or partial permutations, for which we give optimal on-line routing algorithms on the hypercube and shuffle-exchange network. For well-formed words of parentheses our algorithm establishes communication between all matching pairs in logarithmic time. It can be applied to the membership problem for certain subclasses of deterministic context-free languages, such as Dyck languages, and to a number of problems dealing with algebraic expressions.

We present a parallel algorithm for the two processor scheduling problem. This algorithm constructs an optimal schedule for unit execution time task systems with arbitrary precedence constraints using a polynomial number of processors and running in time polylog in the size of the input. Whereas previous parallel solutions for the problem made extensive use of randomization, our algorithm is completely deterministic and based on an interesting iteration technique. It is of independent relevance for two more reasons. It provides another example for the apparent difference in complexity between decision and search problems in the context of fast parallel computation, and it gives an $\mathcal{NC}$-algorithm for the matching problem in certain restricted cases.

An algorithm is presented for the general Petri net reachability problem. It is based on a generalization of the basic reachability tree construction which is made symmetric with respect to the initial and final marking. Sets of transition sequences described by finite automata are used for approximations to firing sequences, and the approximation error is assessed by Presburger expressions. The approximation algorithm is iterated until a sufficient criterion for reachability is satisfied. The exact computational complexity of our algorithm is an open problem.

We introduce new paradigms for the construction of efficient parallel graph algorithms. These paradigms, called filtration and funnelled pipelining, are illustrated with VLSI circuits for computing connected components, minimum spanning forests, and biconnected components. These circuits use realistic I/O schedules and require time and area of O(n1+ε). Thus they are essentially optimal. Filtration is a technique used to rapidly discard irrelevant input data. This greatly reduces storage, time, and communications costs in a wide variety of problems. A funnelled pipeline is obtained by building a series of increasingly thorough filter stages. Transition times along such a pipeline of filters form an exponentially increasing sequence. The increasing amount of time exactly balances the increasing degree of filtration. This balance makes possible the cascaded filtration critical to the minimum spanning forest and the biconnected components algorithms.

An algorithm is presented for the general Petri net reachability problem based on a generalization of the basic reachability construction which is symmetric with respect to the initial and final marking. Sets of transition sequences described by finite automata are used for approximations to firing sequences, and the approximation error is assessed by uniformly constructable Presburger expressions. The approximation algorithm is iterated until a sufficient criterion for reachability can be given, not-withstanding the remaining uncertainty.

If the reachability set of a Petri net or vector addmon system is fimte, it can be effectively constructed.Furthermore, this finiteness is decidable The complexity of dectsion procedures for the containment and equality problem of f'lmte reachabihty sets rs investigated, and it is shown by reducing a bounded version of Hilbert's Tenth Problem to the finite containment problem that these two problems are extremely hard--that, in fact, the complexity of each decision procedure exceeds any primitive recursive functmn mfimtely often The funte containment and equality problems are thus the first uncontrived decidable problems which are not primitive recursive KEY WORDS AND PHRASES.incluston problem, reachabihty set, Petn net, pdmmve recurs~ve complexity