Autoren: Hans A. Kestler, Jochen Messner, André Müller, Rainer Schuler

Many experiments in the biomedical field generate vast amounts of data. This is especially true for microarray experiments which measure the expression levels of thousands of genes simultaneously. In this context the display of functional information attributed to the individual gene is important to obtain an overview of the ma jor processes involved. This set data can be displayed as Euler/Venn diagrams in which the circle size corresponds to the cardinality of the set. Efficient algorithms for the calculation of intersections of circles and their resulting boundary have not been published so far. We present two algorithms (one optimal) for intersecting these different sized circles to display set relationships.

PDF

Autoren: Manfred Reichert, Peter Dadam, Martin Jurisch, Ulrich Kreher, Kevin Göser, Markus Lauer

To provide effective support, process-aware information systems (PAIS) must not freeze existing business processes. Instead they should enable authorized users to deviate on-the-fly from the implemented processes and to dynamically evolve them over time. While there has been a lot of work on the theoretical foundations of dynamic process changes, there is still a lack of PAIS implementing this dynamics. Designing the architecture of respective technology constitutes a big challenge due to the high complexity coming with dynamic processes. Besides this, performance, robustness, security and usability of the system must not be affected by the added flexibility. In the AristaFlow project we have taken a holistic approach to master this complexity. Based on a conceptual framework for flexible process enactment and dynamic processes, we have designed a sophisticated architecture for next generation process management technology. This paper discusses major design goals and basic architectural principles, gives insights into selected system components, and shows how change support features can be realized in an integrated and effective manner.

PDF

Autor: Frank Raiser

Constraint programming often involves global constraints, which have been cataloged in [1] and for which various custom filtering algorithms have been published. This work presents a semi-automatic generation of CHR solvers for the set of global constraints which can be defined by specific automata described in [2]. The solvers only need to be generated once and achieve arc-consistency for over 40 global constraints.

PDF

Autoren: Ramin Tavakoli Kolagari, Alexander Raschke, Matthias Schneiderhan, Ian Alexander

Die Entwicklung innovativer Systeme ist trotz intensiver Forschung auf diesem Gebiet eine herausfordernde Arbeit. Innovative eingebettete Systeme in der Automobilindustrie stellen hohe Anforderungen an die Entwickler, da diese zumeist Systeme für einen konkreten Bedarf entwickeln, der in dieser Ausprägung bisher nicht existiert und damit auch keine dedizierten Stakeholder befragt werden können. Im Zuge dieser Entwicklungsarbeiten wird ein intensives Domain Engineering betrieben, bei dem viel Wissen über die zu entwickelnde Domäne angesammelt wird, das auch für die Fortentwicklung der Systeme relevant ist. Da in der Industrie Wiederverwendung eine beachtliche Rolle spielt, da durch sie eine Senkung der Entwicklungskosten sowie eine Steigerung der Qualität unterstützt wird, muss man von Beginn einer Entwicklung an die Wiederverwendbarkeit von Wissen oder Komponenten unterstützen. Software-Produktlinien sind eine besonders erfolgreiche Technik, um Wiederverwendung zu gestalten. In dem vorliegenden Bericht beschreiben wir ein Experiment, das zwei unterschiedliche Beschreibungstechniken für das während der frühen Phase der Innovationsentwicklung anfallende Wissen vergleicht, um es für die Einbettung der Innovation in eine Software-Produktlinie zu nutzen. Verglichen werden klassische Sitzungsprotokolle mit Entscheidungsmodellen, die auf der Arbeit von James Dewar und Stephen Toulmin aufsetzen. Das in diesem Bericht beschriebene Experiment wurde als Praktikum für Studierende im Hauptstudium an der Universität Ulm im Sommersemester 2005 durchgeführt. Die aus dem Experiment gewonnenen Hinweise deuten an, dass eine sinnvolle Verwendung von den von uns vorgestellten Entscheidungsmodellen mit weniger Aufwand zu einem besseren Verständnis der Domäne der Innovation insgesamt führt und dieses Wissen auch leichter anderen Personen zugänglich ist.

PDF

Autoren: Markus Kalb, Claudia Dittrich, Peter Dadam

Ecient support of moving objects on networks is receiving increasing attention. An interesting issue is to analyze the interactions of objects within a network. In order to support queries related to the dynamic behaviour of two or more moving objects in conjunction, topological information must be maintained which relates the moving objects to the network as well as the moving objects among another. As typical application areas tend to generate large data volumes, an adequate storage representation and the resulting effort to evaluate such topological relationships are crucial in practice. To face that challenge, we propose a new representation model for moving objects, which enables a rather compact representation of both, information on the network and information on the moving objects on this network. This, in turn, allows to eciently evaluate respective queries.

PDF

Autoren: Matthias Frank, Frank Kargl, Burkhard Stiller (Hg.)

Bereits zum fünften Mal treffen sich dieses Jahr Forscher aus Deutschland und den europäischen Nachbarländern, um unter dem Dach des “Workshop on Mobile Ad-hoc Networks” Erfahrungen und Forschungsergebnisse auszutauschen und neue Ideen zu diskutieren.

PDF

Autoren:  M. Maucher, U. Schöning, H.A. Kestler

When designing and analyzing randomized algorithms, one usually assumes that a sequence of uniformly distributed, independent random variables is available as a source of randomness. Implementing these algorithms, however, one has to use pseudorandom numbers. The quality of the used pseudorandom number generator may severely influence the quality of an algorithm’s output. We examined the effect of using low quality pseudorandom numbers on the performance of different search heuristics like Simulated Annealing and a basic evolutionary algorithm.

PDF

Autor: Henning Wunderlich

We establish a new connection between the theory of Berge graphs (perfect graphs) and communication complexity. We discover a new class of square-free Berge graphs, the class of beautiful graphs, and make progress towards their characterization: on the one hand, we give a complete list of forbidden induced subgraphs of order ≤ 7, on the other hand, we show that every square-free bipartite graph is beautiful, and, as the main result, we characterize the beautiful line graphs of square-free bipartite graphs.

PDF

Autor: Henning Wunderlich

Various simplied or improved, and partly corrected well-known implicit characterizations of the complexity classes FPTIME and NC are presented. Primarily, the interest is in simplifying the required simulations of various recursion schemes in the corresponding (implicit) framework, and in developing those simulations in a more uniform way, based on a step-by-step comparison technique, thus consolidating groundwork in implicit computational complexity.
PDF

Autor: Henning Wunderlich

PDF

Autoren: M. Maucher, U. Schöning, H.A. Kestler

This article explains the various notions of pseudorandomness, like Martin-Löf randomness, Kolmogorov complexity, Shannon entropy and quasi-randomness. We describe interconnections between these notions and describe how the non-computable notions among them are relaxed and used in practice, for example in statistics or cryptography. We give examples for pseudorandom generators relating to these notions and list some dependancies between the quality of pseudorandom numbers and its impact on some properties of randomized algorithms using them.

PDF

Autor: Henning Wunderlich

We prove Toda's Theorem in the context of structural communication complexity, i.e. PHcc Í BP · ÅPcc Í Pcc (#Pcc) = Pcc (PPcc). The class PSPACEcc was defined via alternating protocols with O(log n) many alternations. We consider the class BP · ÅPcc of Toda's Theorem, and show that every language in this class can be decided with alternating protocols using O(log n/ log log n) many alternations. The proof is based on a new alternating protocol for the inner product function IP with O(log n/ log log n) many alternations.

PDF

Autoren:  Manfred Reichert, Peter Dadam

In dynamic environments it must be possible to quickly implement new business processes, to enable ad-hoc deviations from the defined business processes on-demand (e.g., by dynamically adding, deleting or moving process activities), and to support dynamic process evolution (i.e., to propagate process schema changes to already running process instances). These fundamental requirements must be met without affecting process consistency and robustness of the process-aware information system. In this paper we describe how these challenges have been addressed in the ADEPT2 process management system. Our overall vision is to provide a next generation technology for the support of dynamic processes, which enables full process lifecycle management and which can be applied to a variety of application domains.

PDF