Universität Stuttgart
Permanent URI for this communityhttps://elib.uni-stuttgart.de/handle/11682/1
Browse
Search Results
Item Open Access Automatic synthesis of distributed transition systems(2006) Stefanescu, Alin; Esparza, Javier (Prof. Dr.)This thesis investigates the synthesis problem for two classes of distributed transition systems: synchronous products and asynchronous automata. The underlying structure of these models consist of local automata synchronizing on common actions. The synthesis problem discussed is as follows: Given a global specification as a transition system TS and a distribution pattern D, find a distributed transition system over D whose global state space is equivalent' to TS. As criteria for the correctness of the (distributed) implementation vs. the specification (i.e., their equivalence') we use: transition system isomorphism, language equivalence, and bisimilarity respectively. In particular, the synthesis of asynchronous automata modulo language equivalence is a notoriously hard problem solved by Zielonka at the end of the 80s. One of the motivations behind our work was to bring this theory closer to practical applications. From the theoretical point of view, we conduct a detailed analysis of the synthesis problem for both models of distributed systems, look at effective algorithmic approaches and draw a map of computational complexity results. E.g., we provide several matching lower and upper complexity bounds for the distributed implementability problem. From the practical perspective, we provide prototype implementations for most of the synthesis algorithms discussed in the thesis. Moreover, we offer assistance when a given specification is not distributable by trying to modify this specification such that distributed synthesis can be applied. By using several heuristics to overcome the classical state space explosion, we are able to automatically generate small distributed algorithms for problems such as mutual exclusion.Item Open Access Investigating dynamics by multilevel phase space discretization(2006) Fundinger, Danny Georg; Levi, Paul (Prof. Dr.)The subject of the thesis is the numerical investigation of dynamical systems. The aim is to provide approaches for the localization of several topological structures which are of vital importance for the global analysis of dynamical systems, namely, periodic orbits, the chain recurrent set, repellers, attractors and their domains of attraction as well as stable, unstable and connecting manifolds. The techniques introduced do not require any a priori knowledge about a system, and are also not restricted by the stability of the solution. Furthermore, they can generally be applied to a wide range of dynamical systems. Two theoretical concepts are considered to be at the center of the research - symbolic analysis and the RIM method. The underlying basic approach for both of them is multilevel phase space discretization. This means that a part of the phase space, the area of investigation, is subdivided in a finite number of sets. Then, instead of each point of the phase space, only these sets are subject of further analysis. The main target of every method proposed is to find those sets which contain parts of the solution and subdivide them into smaller parts until a desired accuracy is reached. In case of symbolic analysis, a directed graph is constructed which represents the structure of the state space for the investigated dynamical system. This graph is called the symbolic image of the focused system and can be seen as an approximation of the system flow. The theoretical background regarding the symbolic image graph as well as the constructive methods applied on it were already described in a series of works by G. Osipenko. In this work, strategies are introduced for a practical application. This requires the extension of the theoretical concepts and the development of appropriate algorithms and data structures. In practice, it turned out that these aspects are essential cornerstones for the usability of the discussed methods. Also some sophisticated tunings of the basic methods are proposed in order to extent the field of practical investigation. Although symbolic analysis can be seen as the main stimulation of this work, the investigation was not limited to it. Indeed, several shortcomings regarding the solution of some problems can be observed if the method is applied in practice. This led to the development of the RIM method. The core intention of the method is to solve the root finding problem. The standard approach toward this task is the application of an iteration scheme based on the Newton method. However, it has shown that such Newton schemes have several structural disadvantages which are especially crucial in the context of the fields of investigation which are relevant to this work. The RIM method proposes an alternative approach which does not require the application of any Newton-like method. Numerical case studies revealed that in several nontrivial scenarios the RIM method provides better results than both, symbolic analysis as well as Newton-based methods. Two applications of the RIM method for the investigation of dynamical systems are provided. One of them is the detection of periodic points. The other is the computation of stable manifolds. The proposed methods contribute not only to the direct investigation and simulation of specific dynamical processes but also to the research in the field of dynamical system theory in general. This is due to the fact that progress in theory depends to a large extent on the observation and investigation of phenomenons. These phenomenons can often only be revealed, analyzed and verified by numerical experiments. The presented numerical case studies give some concrete examples for the application of the methods. Hereby, the dynamical models are taken from different fields of scientific research, like geography, biology, meteorology, or physics.Item Open Access Interactive visualization methods for mobile device applications(2006) Diepstraten, Joachim; Ertl, Thomas (Prof.)The number of mobile devices today already outnumbers the installed desktop PCs and this gap will further widen in the future since the market for desktop PCs is stagnating but is still growing for mobile devices. For example, the cellular phone is one of the most widespread devices that can display graphical content and its functionality is constantly increasing. Even with the increased functionality on recent mobile devices bringing interactive graphics and visualization methods to these devices is not as easy as it might appear to be. Strategies and ideas that work for desktop machines cannot necessarily be transferred to mobile devices because they have very different characteristics. The purpose of this thesis is to exactly address this problem. The current limitations of these devices -- limited processing power, small amount of memory, low bandwidth, limited network capacities, small display area -- that hinder the usage of current visualization applications on these devices are identified. In order to overcome them, several different strategies are presented that allow interactive 3D graphic solutions to run on mobile devices. These strategies take advantage of different properties of a mobile device, e.g., network speed. Which strategy should be employed for a graphical application can be decided based on the properties of the device that suit best to the strategy. Moreover, algorithms for presenting data in a resource friendly, user recognizable form but at the same time taking account of the display limitations are introduced by addressing ideas in illustrative and artistic rendering. A special focus in this thesis is on the representation of transparency that plays a significant role in extending the usable space for visualizing information. In this thesis several strategies taken from artistic rendering have been successfully applied to the context of mobile rendering solutions. Additionally, a 3D graphical user interface was designed that is well suited to solve spatial problems in mobile devices and allows developers to build new classes of modern user interfaces. All the new algorithms explained in this thesis do not only extend the capabilities of bringing interactive 3D graphics to mobile device, but can for example also be used for enhancing the richness of visualization or non-photorealistic rendering methods in any sort of interactive environment.Item Open Access Hardware-beschleunigte Volumenvisualisierung auf adaptiven Datenstrukturen(2006) Weiler, Manfred; Ertl, Thomas (Prof. Dr.)In vielen Disziplinen und Anwendungsgebieten spielen Volumendaten heutzutage eine immer wichtigere Rolle und der Einsatz von Graphik-Hardware stellt eine gute Möglichkeit dar, den mit der Volumenvisualisierung verbundenen Berechnungsaufwand zu meistern. Die bisher auf Graphikkarten übliche relativ starre Verarbeitungspipeline beschränkt ihren Einsatz jedoch auf wenige Typen von Volumendaten, insbesondere uniforme 3D Gitter, deren Struktur sich effizient auf die Mechanismen auf der Graphikkarte abbilden lässt. Mit der kürzlich eingeführten freien Programmierbarkeit von Graphikkarten ist es zunehmend möglich, die massive Rechenleistung der Graphikchips, welche die Fähigkeiten aktueller Universalprozessoren bei weitem übersteigt, für die Visualisierung von Volumendaten auf adaptiven Datenstrukturen einzusetzen. Am Beispiel dreier wichtiger Vertreter dieser Gattung von adaptiven Datenstrukturen, Finite-Elemente-Netze in ihrer Ausprägung als Tetraedergitter, lokale Gitterverfeinerungen sowie gitterlose Punktrepräsentationen, untersucht diese Arbeit, in wieweit sich die dafür erforderlichen komplexen Visualisierungsalgorithmen durch den Einsatz moderner Graphik-Hardware beschleunigen lassen. Ziel es dabei, möglichst viele Teile der Berechnung in den Verantwortungsbereich der Graphikkarte zu bringen, um auch in Zukunft von dem raschen Fortschritt bei der Entwicklung von Graphik-Hardware zu profitieren. Ein wichtiges dabei zu untersuchendes Problemfeld stellt das Zusammenspiel der unterschiedlichen involvierten Berechnungseinheiten (Hauptprozessor, Vertexprozessor und Fragmentprozessor auf der Graphikkarte) dar. Die Geschwindigkeitsoptimierung durch ausgewogenene Balance wird in der vorliegenden Arbeit durch unterschiedliche Algorithmen zur Visualisierung von Tetraedergittern demonstriert, die sukzessive identifizierte Flaschenhälse bei der Berechnung und der Kommunikation mit nachgelagerten Einheiten und dem Speicher beseitigen. Am Ende steht ein Hardware-basierter Ray Casting-Algorithmus für Tetraedergitter, der vollständig auf der Graphik-Hardware abläuft. Da Algorithmen, die auf der Graphikkarte ablaufen, ihre Daten aus dem Speicher der Graphikkarte beziehen, werden weiterhin Möglichkeiten zur Kompression betrachtet, um die maximale Größe der verarbeitbaren Datensätze zu erhöhen. Es wird eine neue kompakte Datenstruktur für Tetraedergitter vorgestellt, welche sowohl die Tetraederattribute als auch die Konnektivität der Tetraeder speichert und als Basis zur Visualisierung mittels Ray Casting dienen kann. Für punktbasierte Daten wird außerdem eine neue kompakte prozedurale Kodierung auf der Grundlage von radialen Basisfunktionen entwickelt, welche durch die Möglichkeit der Dekodierung mittels der programmierbaren Fragmenteinheit mit einer Vielzahl von Visualisierungslagorithmen kombinierbar ist und durch die vorgelagerte Kodierung anderer Datenstrukturen wie uniformer Gitter, Tetraedergitter oder gitterloser Daten eine universelle Visualisierungslösung darstellt. Eine weitere Option zur interaktiven Visualisierung von Tetraedergittern bietet die Abtastung auf adaptiv verfeinerten uniformen Volumengittern, die besser für die Verarbeitung auf der Graphikkarte geeignet sind. Hier ermöglicht die Beschleunigung der Abtastung mittels Graphik-Hardware die dynamische Berechnung, jeweils entsprechend den Parametern des aktuell dargestellten Bildes. Die sonst beim Resampling auftretenden charakteristischen Probleme wie hoher Speicherbedarf, geringe Interaktionsraten oder niedrige Darstellungsqualität werden dadurch vermieden beziehungsweise minimiert. Für typische Probleme, die bei der Visualisierung auf der Basis adaptiv verfeinerter uniformer Gitter auftreten, wie inkonsistente Interpolation zwischen unterschiedlichen Gitterbereichen oder Artefakte, die durch eine adaptive Abtastung auftreten, werden Lösungsansätze präsentiert. Implementierungsaspekte einer adaptiven Volumendarstellung auf uniformen Gittern werden im Rahmen einer neuartigen Software-Architektur mit flexiblen und erweiterbaren Shadern betrachtet. Sie erlaubt es, die Visualisierungsalgorithmen einfach auf die spezielle Graphik-Hardware der Zielplattform anzupassen, was in Anbetracht der heterogenen Graphikkarten-Landschaft einen wichtigen Baustein für die Entwicklung effizienter Visualisierungslösungen darstellt. Darüberhinaus wird gezeigt, wie sich programmierbare Graphik-Hardwere im Umfeld von virtuellen Umgebungen durch Hardware-beschleunigte Bildkompression und -dekompression geschwindigkeitssteigernd einsetzen lässt. Die Arbeit bringt alle vorgestellten Algorithmen in einen Gesamtzusammenhang, der es erlaubt gemeinsame Gestaltungsrichtlinien für die erfolgreiche Umsetzung von Visualisierungs-Algorithmen auf Graphik-Hardware zu extrahieren. Diese können anderen Forschern als Muster und zur Anregung dienen und so die Entwicklung weiterer Hardware-beschleunigter Algorithmen inspirieren.Item Open Access Halbordnungs- und Reduktionstechniken für die automatische Verifikation von verteilten Systemen(2006) Schröter, Claus; Esparza, Javier (Prof. Dr.)Das Hauptproblem bei der automatischen Verifikation von verteilten Systemen unter Verwendung von Model-Checking-Verfahren besteht in der Zustandsraumexplosion der Ausgangssysteme. Dieses bedeutet, daß sogar die Spezifikation eines kleinen Systems oftmals einen großen Zustandsraum aufspannt, da dieser exponentiell in der Größe des Ausgangssystems wachsen kann. In der Vergangenheit wurden verschiedene Techniken vorgeschlagen, um diese Problematik in den Griff zu bekommen. Diese können klassifiziert werden in Techniken, die auf eine implizite, kompakte Repräsentation des gesamten Zustandsraums abzielen, zum Beispiel codiert als BDD, oder die unter Verwendung von Abstraktionen oder Halbordnungsreduktionen eine reduzierte Zustandsraumrepräsentation verwenden. Eine dritte Klasse von Techniken stützt sich auf die Halbordnungssicht auf nebenläufige Berechnungen, und Systemzustände werden hier implizit durch die Verwendung azyklischer Petrinetze repräsentiert. Sehr populär darunter ist die Technik von McMillan zur Erzeugung endlicher, vollständiger Präfixe von Petrinetzentfaltungen. Das Ziel dieser Arbeit besteht darin, effiziente Halbordnungs- und Reduktionstechniken für die automatische Verifikation von verschiedenen Petrinetzklassen zu analysieren, zu erweitern, zu implementieren und experimentell zu vergleichen. Eine der Hauptfragestellungen auf dem Gebiet der automatischen Verifikation untersucht die Erreichbarkeit von Systemzuständen, da viele Sicherheitseigenschaften eines Systems auf einfache Erreichbarkeitsfragen zurückgeführt werden können. Als typisches Beispiel sei hier die Eigenschaft zum wechselseitigen Ausschluß von nebenläufigen Prozessen erwähnt. In dieser Arbeit werden vier Verfahren betrachtet, die das Erreichbarkeitsproblem für 1-sichere Petrinetze unter Verwendung von Entfaltungspräfixen exakt lösen. Es werden zwei Halbentscheidungsverfahren betrachtet, die das Erreichbarkeitsproblem für 1-sichere Petrinetze unter Verwendung von Techniken der linearen Programmierung zu lösen versuchen. Die Verfahren werden anhand von experimentellen Ergebnissen miteinander verglichen, und es wird eine Empfehlung hergeleitet, welche Verfahren für praktische Belange geeignet zu sein scheinen. Es wird gezeigt, daß das PSPACE-vollständige Erreichbarkeitsproblem für 1-sichere Petrinetze in ein (möglicherweise exponentiell größeres) NP-vollständiges Problem überführt werden kann, sofern Entfaltungstechniken eingesetzt werden. Eine weitere wichtige Fragestellung auf dem Gebiet der automatischen Verifikation beschäftigt sich mit dem Nachweis von Sicherheits- und Lebendigkeitseigenschaften, die in Form von temporalen Logiken wie beispielsweise CTL oder LTL formuliert werden. Es werden Reduktionsregeln für den Nachweis von LTL-X-Eigenschaften betrachtet, die in zwei Kategorien eingeteilt werden können: Regeln, die lineare Programmierung unter Verwendung von Invarianten oder impliziten Stellen einsetzen, und Regeln, die lokale Netzreduktionen betrachten. Es wird gezeigt, daß die Bedingungen für die Anwendbarkeit einiger lokaler Netzreduktionen abgeschwächt werden können, sofern man LTL-X-Eigenschaften mit einem Verfahren von Esparza und Heljanko nachweist. Anhand von experimentellen Ergebnissen wird gezeigt, daß die Verifikationszeit für eine LTL-X-Eigenschaft eines Systems signifikant verringert werden kann, sofern dieses mit den vorgeschlagenen Reduktionsregeln vorverarbeitet wird. Schließlich wird der von Esparza und Heljanko vorgestellte entfaltungsbasierte Ansatz zum Nachweis von LTL-X-Eigenschaften 1-sicherer Petrinetze auf eine höhere Petrinetzklasse übertragen. Anhand von experimentellen Ergebnissen wird der in dieser Arbeit vorgestellte Ansatz mit dem Ansatz von Esparza und Heljanko sowie dem Model-Checker SPIN verglichen. Die Ergebnisse zeigen, daß der in dieser Arbeit verwendete Model-Checker dem Model-Checker von Esparza und Heljanko in allen Beispielen, und SPIN gegenüber in einigen Beispielen überlegen ist.Item Open Access Scalable deterministic logic built-in self test(2006) Gherman, Valentin; Wunderlich, Hans-Joachim (Prof. Dr. rer. nat.)The core-based design style of integrated circuits (ICs) helps to manage the development challenges brought by the ever increasing complexity of integrated systems and the ever tighter time-to-market. Nevertheless, test-related problems are still far away from having a unitary and satisfactory solution, especially in the system on a chip (SOC) context. For the test of ICs two reference approaches are available: external testing and built-in selftest (BIST), out of which a variety of hybrid test strategies are obtained by test resource partitioning (TRP). The final goal is to provide advantageous tradeoffs of the test evaluation indicators like: test development and application cost, hardware overhead, fault coverage, etc. BIST offers support for in-field, on-line, burn-in and at-speed test that is indispensable for delay fault testing. Moreover, tradeoffs between fault coverage, hardware overhead and test length are possible. External testing is characterized by flexibility, reduced hardware overhead and high fault coverage for a given test length. Deterministic logic BIST (DLBIST) is an attractive test strategy, since it combines the advantages of deterministic external testing and pseudo-random logic BIST (LBIST). Unfortunately, previously proposed DLBIST methods are unsuited for large ICs, since computation time and memory consumption of the DLBIST synthesis algorithms increase exponentially, or at least cubically, with the circuit size. In this work, a novel procedure for the development of the so-called bit-flipping DLBIST scheme is proposed, which has nearly linear complexity in terms of both computation time and memory consumption. This new method is based on the use of Binary Decision Diagrams (BDDs). The efficiency of the employed algorithms is demonstrated for industrial designs containing up to 2M gates. The embedded test sequences obtained by mapping deterministic cubes to pseudo-random sequences are also evaluated with respect to the coverage of non-target defects, which are modeled with the help of resistive bridging faults. The experimental results prove that both deterministic cubes and pseudo-random sequences are useful for detecting non-target defects. Moreover, possible tradeoffs between test length, hardware overhead, fault coverage and nontarget defect coverage are analyzed. This work additionally presents the results of extending the bit-flipping DLBIST scheme such that it also supports the transition fault testing besides the stuck-at fault testing. Transition faults model defects which are responsible for the incorrect operation of the core under test (CUT) at the desired speed. The importance of these defects is continuously enhanced by the ever increasing clock rates and integration density of today s circuits. Experimental results obtained for large industrial benchmark designs are reported. No pure DLBIST approach for the test of delay faults in circuits with standard scan design has been published so far. In order to decrease the logic overhead of DLBIST, an innovative way of constructing efficient implementations for the involved Boolean functions (e.g. bit-flipping functions) is presented. A key feature of these functions is their incomplete specification which is based on large don t care sets (sets of input assignments for which it does not matter whether they are mapped to 0 or 1 ). Reduced ordered Binary Decision Diagrams (ROBDD) are used for representing and manipulating the involved functions and multi-level implementations are obtained based on the use of free BDDs (FBDD). Experimental results show that for all the considered functions, implementations are found with a significant reduction of the gate count as compared to a state-of-the-art multi-level synthesys tool (SIS [Sen92]) or to methods offered by a state-of-the-art BDD package. This performance is due to a reduction of the node count in the corresponding FBDDs and a decrease in the average number of gates needed to implement the FBDD nodes. The experimental results obtained for large industrial benchmark designs show that DLBIST may be well suited for use in special segments of IC development, like the ones dealing with security chips or hard cores.Item Open Access Methoden zur intuitiven Modifikation und interaktiven Darstellung von großen Finite-Element-Modellen(2006) Rose, Dirc; Ertl, Thomas (Prof. Dr.)Die Entwicklung neuer Fahrzeugtypen im Automobilbau unterliegt zunehmend einem steigenden wirtschaftlichen und damit zeitlichem Druck. Um diesem Druck entgegenzuwirken, wurde unter anderem mit der Entwicklung und Einführung virtueller Simulationstechniken vor einigen Jahren ein wesentlicher Schritt hin zu kürzeren Evolutionszyklen getätigt. Um die dabei eingesetzten Daten - in der Regel Finite-Element (FE)-Modelle - visualisieren und bearbeiten zu können, wurden von verschiedenen Anbietern teilweise spezialisierte Werkzeuge erstellt. Allerdings wurde beim Entwurf der meisten dieser Werkzeuge lediglich auf die reine Funktionalität geachtet, so dass eine intuitive und somit schnell zu erlernende, einfache Bedienbarkeit dieser Anwendungen in der Regel nicht gegeben ist. Zudem werden im Allgemeinen die Möglichkeiten moderner Graphikhardware überhaupt nicht oder nur in geringem Maße ausgenutzt, so dass aufgrund der konventionellen Darstellungsmethoden ein interaktives Arbeiten mit großen Modellen nicht durchführbar ist bzw. mit einer Performanz erfolgt, die hinter aktuellen Möglichkeiten zurückbleibt. Die Dissertation befasst sich daher sowohl mit Methoden zur Optimierung der Qualität als auch der Steigerung der Interaktionsrate bei der Modelldarstellung. Dazu wurden Verfahren entwickelt, welche durch speicherfreundliches Ablegen von Oberflächeninformationen in Texturen auf der Graphikkarte den Einsatz beliebiger Beleuchtungsmodelle und eine pixelexakte Auswertung derselben erlauben. Da bei technischen Komponenten Knicke in der Struktur sich entscheidend auf die Stabilität eines Fahrzeugs auswirken können, werden solche Merkmale gesondert behandelt und hervorgehoben. Bei den im weiteren Verlauf präsentierten Simplifizierungsverfahren zur Performanzsteigerung bei der interaktiven Visualisierung großer FE-Modelle werden spezialisierte Methoden vorgestellt, welche hohe Simplifizierungsraten mit dem Erhalt dieser Merkmale verbinden. Dabei tragen neue Graphiktechnologien und darauf zugeschnittene Algorithmen dazu bei, auch feine Details konservieren zu können - wie z.B. die Anzeige der Umrandung der einzelnen finiten Elemente. Somit ist zwischen Original und simplifiziertem Modell kein visueller Unterschied erkennbar. Diese interaktiven Visualisierungstechniken bilden die Grundlage für intuitive Modifikationsmechanismen, welche es erlauben, benutzerfreundlich und innerhalb kürzester Zeit Standardaufgaben durchzuführen. Dazu zählen die schnelle und bequeme Definition von Bauteilverbindungen und das Erzeugen virtueller Sensorpunkte, welche zur Überprüfung auftretender Kräfte in der experimentellen Simulation unerlässlich sind. Neben diesen vor allem für strukturmechanische Untersuchungen wichtigen Themen wurden Methoden zur interaktiven Verformung bestehender Modellgeometrie entwickelt. Dabei wurde besonderen Wert auf die Flexibilität der Deformationsoperationen unter Anwendung einer intuitiv zu bedienenden Steuerung gelegt. Während der Interaktion ständig durchgeführte Kontrollen der Netzqualität und entsprechende visuelle Rückkopplungsmechanismen sowie auf die Bedürfnisse von FE-Netzen zugeschnittene Optimierungsalgorithmen zur automatischen Behebung der dabei ggf. entstehenden FE-Vernetzungsfehler unterstützen den Anwender bei der Durchführung dieser Aufgaben. Um ein optimales Verständnis zu garantieren, wurden zudem spezielle dreidimensionale Glyphen erstellt, welche die Bearbeitung der erläuterten Aufgaben sinnvoll ergänzen und erleichtern. Räumliche Darstellungs- und Interaktionstechniken können dabei das Verständnis und den Umgang mit einem dreidimensionalen Modell erheblich verbessern. Deshalb wurde der im Laufe der Arbeiten entstandene, mittlerweile kommerziell vertriebene Prototyp um verschiedene Ein- und Ausgabemöglichkeiten erweitert, welche die Einbindung in eine arbeitsplatzbasierte, virtuelle Umgebung ermöglichen. Neuartige Hardware erlaubt zu diesem Zweck sowohl autostereoskopische Visualisierungen als auch haptisch unterstützte Eingabe. Im Hinblick auf die im vorangegangenen Abschnitt vorgestellten Methoden ergeben sich in solch einer immersiven Arbeitsplatzumgebung neue Anforderungen und neue Möglichkeiten, welche entsprechend untersucht und eingebunden wurden. Im Vergleich zu konventionellen bzw. verbreiteten FE-Werkzeugen erlauben die im Rahmen dieser Arbeit entwickelten Verfahren somit ein intuitiveres, angenehmeres, direkteres und damit schnelleres bzw. effektiveres Arbeiten im Umgang mit dreidimensionalen Modellen.Item Open Access Neural dynamics for mobile robot adaptive control(2006) Oubbati, Mohamed; Levi, Paul (Prof. Dr. rer. nat. habil.)In this thesis, we investigate how dynamics in recurrent neural networks can be used to solve some specific mobile robot problems. We have designed a motion control approach based on a novel recurrent neural network. The advantage of this approach is that, no knowledge about the dynamic model is required, and no synaptic weight changing is needed in presence of time varying parameters. Furthermore, this approach allows a single fixed-weight network to act as a dynamic controller for several distinct robots. To generate the robot behavior over time, we adopted the theory of neural fields. We designed a framework to navigate a robot to its goal in an unknown environment without any collisions with static or moving obstacles. In addition, we could optimize the target path through intermediate homebases. This framework has also produced a simple and elegant solution for the problem of moving multiple robots in formation. The objective is to acquire a target, avoid obstacles and keep a geometric configuration at the same time.Item Open Access Acceleration techniques for numerical flow visualization(2006) Stegmaier, Simon; Ertl, Thomas (Prof. Dr.)This thesis addresses the problem of making computer-aided flow visualization more efficient and more effective. More efficient because several new algorithms are presented for accelerating the visualization itself; more effective because accelerated visualization yields more productive work during data analysis. Whether there is a need for acceleration techniques depends on several parameters. Obviously, there is a strong dependence on the available computing hardware: what is reasonable on one hardware platform might be unbearable on another platform. This straightforwardly leads to the idea of switching to another (remote) visualization platform while keeping the researcher's workspace untouched. Alternatively, more efficient use of local hardware resources can be made, a direction followed in this thesis by balancing the workload between the (programmable) graphics hardware and the central processing unit. Instead of exploiting parallel processing, reduced accuracy can be traded for improved interactivity. In this work, this trade-off is made by converting the grid underlying the data to a representation that can be handled more efficiently. In the worst case, neither hardware approaches nor accuracy reduction sufficiently improve the data analysis. Consequently, data reduction must be employed to keep up with human cognition capabilities and limited graphics processing resources. This issue is addressed by flow feature extraction which aims at presenting a highly compact representation of the data. This work thus presents a unique multi-level approach for accelerating flow visualization, considering hardware resources, accuracy requirements, and cognitive issues. Due to the generality of the selected acceleration techniques presented in this thesis, some results do also have impact on other areas of scientific visualization. Furthermore, due to the layered approach addressing the acceleration on multiple abstraction levels, the presented techniques can be used stand-alone as well as in combination to yield a highly flexible toolbox that can be fine-tuned to the respective environment.Item Open Access Logical fragments for Mazurkiewicz traces : expressive power and algebraic characterizations(2006) Kufleitner, Manfred; Diekert, Volker (Prof. Dr.)Mazurkiewicz trace are a model for concurrency. They can be seen as a generalization of words by introducing partial commutation between specific letters. Several logical and language-theoretic characterizations of the variety of monoids DA are known for words. We show which of them also hold for traces and which of them do not hold. An important tool for this task are Ehrenfeucht-Fraisse games. For several logical fragments, we introduce characterizations in terms of these games. They are used to separate logical fragments over traces that have the same expressive power over words. An essential property is, whether one can express concurrency within a fragment or not.