Oberseminar Theoretische Informatik SS 04

Gegenstand des Vortrags sind die theoretischen Eigenschaften des Formalismus der Objekt-Petrinetze, kurz: der Objektnetze. Dieser Formalismus erweitert die Petrinetztheorie insofern, als dass nicht nur Werte als Marken zugelassen sind, sondern sogar Objekte mit innerer Aktivität. Für Objektnetze werden diese Objekte wiederum durch Petrinetze beschrieben, so dass sich "Netze in Netzen" befinden. Die rekursive Verschachtelung von Petrinetzen ist prinzipiell unbeschränkt.

Um Objektnetze in den formalen Kontext der allgemeinen Petrinetztheorie einzuordnen, wird untersucht, welche Ausdrucksmächtigkeit der Formalismus besitzt. Es ist zu klären, inwieweit sich die strukturellen Eigenschaften auf Objektnetze übertragen. Weiterhin sind Entscheidbarkeitsfragen (wie beispielsweise das Erreichbarkeits- oder das Beschränktheitsproblem) zu analysieren.

1. We consider the problem of translational and rotational motion of a geometric object avoiding obstacles of a particular shape. The position and orientation of the geometric object to be moved is represented as a single point in a configuration space. The configurations forbidden to this object, due to the presence of obtacles, can be characterized as regions in this configuration space, called configuration space obstacles. The geometric object to be moved as well as obstacles are defined by non-linear inequalities. The algorithm that computes the configuration space obstacles (so-called Minkowski sum of semi-algebraic point sets) using functional representation of point sets (so-called R-Functions) will be discussed. R-Functions define a potential field, which "moves" the object avoiding any collisions.

2. Domain decomposition method is a well-known family of approaches to parallelization of the numerical solution of Partial Differential Equations (PDE's). In the case of Finite Element Method (FEM), the PDE is reduced to the system of linear algebraic equations. The unknowns in this system are values of the solution function at the particular spatial positions in the entire of the domain. Domain decomposition leads to efficient decoupling of a system of linear equations, which can be solved independently, for example, on several parallel processors. We show, how complicated geometric domains can be represented in functional form using so-called R-Functions. The latter enable one to define complicated domains in terms of it\x{2019}s primitive parts usng set-theoretic operations. We decompose the complicated domain described with the aid of R-Functions into symmetric parts by computing the invariant matrix group of primitive parts. Our recent idea is to facilitate the symbolic abilities of computer algebra and to solve the PDE with symbolic boundary conditions. This allows one to calculate the solution of the PDE only on one of the symmetric parts. The overall solution can be assembled using the symmetry information. This approach allows to speed up the numerical computation by factor 2 to 8. The advancing front triangulation of decomposed parts as well as finite element simulation on the resulting unstructured grid will be discussed.

Es werden die zwei zunächst unzusammenhängende Probleme der Berechnung des Schnittes von Ringen und Moduln sowie der Stratifizierung von linearen Aktionen kompakter Lie Gruppen betrachtet. Die Verbindung zwischen den beiden Problemen liegt in der Invariantentheorie von algebraischen Gruppen.

Es werden neue Algorithmen zur Berechnung des Schnittes von endlich erzeugten graduierten Ringen bzw. graduierten Moduln, und zur Berechnung von Invariantenringen und von Äquivarianten vorgestellt. Weiters wird ein neuer Zugang zur Berechnung von Stratifikationen von Aktionen kompakter Lie Gruppen vorgestellt, der auch die Berechnung von einzelnen Strata ermöglicht. Es wird gezeigt, dass zur Beschreibung eines d-dimensionalen Stratum maximal d Ungleichungen benötigt werden, was sich als optimal herausstellt.

In diesem Vortrag betrachten wir die Entwicklungsschuebe der Verifikationstools im Ueberblick, und gehen danach auf neuere Resultate zur Dekomposition unendlicher Systeme im Detail ein.