05 Fakultät Informatik, Elektrotechnik und Informationstechnik
Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6
Browse
33 results
Search Results
Item Open Access Reachability analysis of multithreaded software with asynchronous communication(2005) Bouajjani, Ahmed; Esparza, Javier; Schwoon, Stefan; Strejcek, JanWe introduce asynchronous dynamic pushdown networks (ADPN), a new model for multithreaded programs in which pushdown systems communicate via shared memory. ADPN generalizes both CPS (concurrent pushdown systems) and DPN (dynamic pushdown networks). We show that ADPN exhibit several advantages as a program model. Since the reachability problem for ADPN is undecidable even in the case without dynamic creation of processes, we address the bounded reachability problem, which considers only those computation sequences where the (index of the) thread accessing the shared memory is changed at most a fixed given number of times. We provide efficient algorithms for both forward and backward reachability analysis. The algorithms are based on automata techniques for symbolic representation of sets of configurations.Item Open Access Emulation von Rechnernetzen zur Leistungsanalyse von verteilten Anwendungen und Netzprotokollen(2005) Herrscher, Daniel J.; Rothermel, Kurt (Prof. Dr. rer. nat. Dr. h. c)Um die Leistung von verteilten Anwendungen und Netzprotokollen in Abhängigkeit von den Eigenschaften der verwendeten Rechnernetze zu analysieren, wird eine Testumgebung benötigt, die Netzeigenschaften zuverlässig nachbilden ("emulieren") kann. Eine solche Testumgebung wird Emulationssystem genannt. Bisher existierende Emulationssysteme sind aufgrund ihrer Architektur entweder nur für sehr kleine Szenarien geeignet, oder sie können nur unabhängige Netzverbindungen nachbilden, und schließen damit alle Netztechnologien mit gemeinsamen Medien aus. In dieser Arbeit werden zunächst verschiedene Architekturvarianten für die Realisierung eines Emulationssystems vorgestellt und bewertet. Für die Variante mit zentraler Steuerung und verteilten Emulationswerkzeugen wird dann detailliert die Funktionalität eines Emulationssystems mit seinen wesentlichen Komponenten beschrieben. Das in dieser Arbeit entwickelte Emulationsverfahren greift auf der logischen Ebene der Sicherungsschicht in den Kommunikationsstapel ein. Auf dieser Ebene werden die beiden Basiseffekte Rahmenverlust und Verzögerung durch verteilte Emulationswerkzeuge nachgebildet. Alle anderen Netzeigenschaften können auf diese Basiseffekte zurückgeführt werden. Um Netztechnologien mit gemeinsamen Medien durch verteilte Werkzeuge nachbilden zu können, wird zusätzlich das Konzept des virtuellen Trägersignals eingeführt. Hierbei werden die Eigenschaften eines Rundsendemediums nachgebildet, indem kooperative Emulationswerkzeuge Rundsendungen zur Signalisierung eines Trägersignals benutzen. Somit kann jedeWerkzeuginstanz lokal ein aktuelles Modell des emulierten gemeinsamen Mediums halten. Auf dieser Basis kann auch das Verhalten von Medienzugriffsprotokollen nachgebildet werden. Die Arbeit deckt auch die wesentlichen Realisierungsaspekte eines Emulationssytems ab. Mit ausführlichen Messungen wird gezeigt, dass das entwickelte System für die Nachbildung von Netzszenarien sehr gut geeignet ist, selbst wenn die nachzubildenden Parameter sich dynamisch ändern. Die entwickelten Werkzeuge sind in der Lage, Netzeigenschaften in einem weiten Parameterbereich realistisch nachzubilden. Mit diesem System steht nun eine ideale Testumgebung für Leistungsmessungen von verteilten Anwendungen und Netzprotokollen in Abhängigkeit von Netzeigenschaften zur Verfügung.Item Open Access Deriving bisimulation congruences in the DPO approach to graph rewriting. Long version(2004) Ehrig, Hartmut; König, BarbaraMotivated by recent work on the derivation of labelled transitions and bisimulation congruences from unlabelled reaction rules, we show how to solve this problem in the DPO (double-pushout) approach to graph rewriting. Unlike in previous approaches, we consider graphs as objects, instead of arrows, of the category under consideration. This allows us to present a very simple way of deriving labelled transitions (called rewriting steps with borrowed context) which smoothly integrates with the DPO approach, has a very constructive natureand requires only a minimum of category theory. The core part of this paper is the proof sketch that the bisimilarity based on rewriting with borrowed contexts is a congruence relation.Item Open Access Situation based process monitoring in complex systems considering vagueness and uncertainty(2004) Rebolledo, Mario; Göhner, Peter (Prof. Dr.-Ing. Dr. h. c.)History has demonstrated during the 20th century that industrial development carries hazards that should not be ignored because they endanger humans, the environment and production facilities. For this reason, continuous development of new production technologies should be accompanied by a comparable development in industrial safety technologies. Safety-critical applications in complex processes are usually based on a precise monitoring of operation conditions, according to a “correct” process operation. The problem is determining if a behavior or an operation condition is “correct”. For this, models are generally used, which are able of reproducing “safe” or “appropriate” process behaviors. The difficulty of precise modeling grows continuously, because of the increasing complexity of the supervised processes. Rigorous deterministic modeling is limited to simple processes, while approximate models based on statistics or Artificial Intelligence techniques, for example, must be restricted to modeling single variables or small subsystems to be manageable and deliver useful information. A monitoring technique usually employed for complex processes relies on abstraction of the process behavior in qualitative models by using symbolic value ranges to represent required information. However, also the applicability of qualitative modeling techniques is eventually restricted by the resulting model size. In this research work, a new process monitoring approach, based on qualitative models, efficiently depicts valuable vague and uncertain information that is currently discarded during the modeling. The proposed method expands the ability of Situation-based Qualitative Modeling and Analysis (SQMA) to monitor complex processes by integrating elements of the Rough Set Theory and Stochastic Qualitative Automata. The resulting models are considerably more precise than other similar-sized qualitative models. At the same time, the new method develops more compact and precise qualitative models than traditional qualitative models of the same precision.Item Open Access Verfahren zur Unterstützung der Arbeitsabläufe bei der Crash-Simulation im Fahrzeugbau(2004) Frisch, Norbert; Ertl, Thomas (Prof. Dr.)Der starke internationale Wettbewerb in der Automobilindustrie zwingt die Unternehmen zu immer kürzeren Produktzyklen bei gleichzeitiger Reduzierung der Kosten bei der Fahrzeugentwicklung. Die passive Sicherheit ist dabei ein Thema von zunehmender Bedeutung in der Karosserieentwicklung. Die Optimierung der passiven Sicherheit erfolgt heute vor allem mit Hilfe von Crash-Simulationen am Rechner. Im Rahmen der vorliegenden Arbeit wurden Verfahren zur Vorbereitung (Preprocessing) und Steuerung von Crash-Simulationen entwickelt. Damit lassen sich Crash-Simulationen effizienter und bereits in der frühen Phase der Karosserieentwicklung durchführen, in der Änderungen noch mit wenig Aufwand verbunden sind. Die Forschungsarbeiten wurden im Rahmen der BMBF-Verbundprojekte AutoBench und AutoOpt und in enger Zusammenarbeit mit dem Automobilhersteller BMW realisiert. Ziel war die Entwicklung von Softwareprototypen zur Unterstützung der Berechnungsingenieure bei der Durchführung von Crash-Simulationen. Zunächst werden Techniken zur Erkennung, Visualisierung und Beseitigung der bei der Diskretisierung des CAD-Modells entstandenen Netzinkonsistenzen präsentiert. Ergänzt werden diese Verfahren durch einen Algorithmus zur Gitterrelaxation, der die Gleichmäßigkeit der Finiten Elemente nach der Beseitigung von Netzinkonsistenzen wiederherstellt. Anschließend wird ein Verfahren zur Flanscherkennung beschrieben, welches als Grundlage für weitere Algorithmen dient. Darauf aufbauend wird eine Vorgehensweise zur automatischen Definition von Schweißpunktlinien auf Flanschen vorgestellt. Ein breites Spektrum von Änderungen der Geometrie von Bauteilen durch Verformung bietet die sogenannte Free-Form Deformation. Im Rahmen dieser Arbeit wurde dieses Verfahren weiterentwickelt und hinsichtlich Benutzerfreundlichkeit und Effizienz angepasst. In Verbindung mit der Flanscherkennung wurde darauf aufbauend ein iterativer Algorithmus zur Justierung des Abstandes von Flanschen entwickelt. Damit können außerdem Durchdringungen von Finiten Elementen auf Flanschen behoben werden. Beim sogenannten Massentrimm geht es schliesslich um die vereinfachte Darstellung von nichttragenden Teilen. Dies vereinfacht den Berechnungsaufwand, da weniger Finite Elemente bei der Simulation berücksichtigt werden müssen. Durch die in dieser Arbeit entwickelten Preprocessing-Verfahren lässt sich das Finite-Elemente-Netz für die Simulation aufbereiten, und es können Änderungen und Ergänzungen am Netz vorgenommen werden. So kann z.B. die Auswirkung kleiner Änderungen auf das Simulationsverhalten rasch untersucht werden, und durch Ergänzung eines noch unvollständigen Finite-Elemente Modells lassen sich bereits in der frühen Entwicklungsphase Erkenntnisse über das Crashverhalten gewinnen. Die hier vorgestellten Verfahren wurden innerhalb einer Anwendung zur Visualisierung und Modellierung von Finite-Elemente-Modellen realisiert. Zusätzlich wurde diese Anwendung an die Integrationsumgebung CAE-Bench angebunden. CAE-Bench bietet eine Web-basierte Benutzerführung und eine einheitliche Bedienoberfläche für die verschiedenen Anwendungen bei der Crash-Simulation. Es wurde ein spezielles Java-Applet entwickelt, welches in die CAE-Bench Web-Seite eingebettet wird. Dieses Applet kommuniziert mit der Anwendung über CORBA und mit der CAE-Bench Web-Seite mit Hilfe von Java und Javascript Methodenaufrufen. Eine weitere CORBA-Schnittstelle der Anwendung ermöglicht den Abruf und die Visualisierung von Zwischenergebnissen der laufenden Simulation. So lässt sich frühzeitig Einfluss auf die Simulation nehmen, ein Vorgehen, das als Simulation Steering bezeichnet wird. Die vorliegende Arbeit kombiniert Ansätze aus den verschiedenen Bereichen der Informatik, z.B. aus dem Bereich der geometrischen Algorithmen, der Computergraphik, der Visualisierung und der geometrischen Modellierung, sowie aus dem Bereich der Benutzerschnittstellen und der Web-basierten und Middleware-Technologien. Durch die Beiträge dieser Arbeit wird eine schnelle und frühzeitige Durchführung von Crash-Simulationen unterstützt. Dies führt durch Simultaneous Engineering zu einer signifikanten Verkürzung der Entwicklungszeiten bei der Fahrzeugkonstruktion.Item Open Access Entwicklung hybrider Komponentenmodelle zur Prozessüberwachung komplexer dynamischer Systeme(2004) Manz, Susanne; Göhner, Peter (Prof. Dr.-Ing. Dr. h. c.)Für die Automatisierung kontinuierlich-diskreter technischer Prozesse ist neben der Realisierung der Steuerungs- und Regelungsfunktionen auch die automatische Überwachung des bestimmungsgemäßen Betriebs von großer Bedeutung. In ingenieurtechnischen Anwendungen werden zur Prozessüberwachung und Diagnose häufig modellbasierte Lösungen mit dem Ziel betrachtet, eine möglichst genaue Beschreibung der betreffenden technischen Anlage zu erhalten. Jedoch ist besonders für komplexe dynamische Systeme das Aufstellen und Betreiben eines mathematischen Modells zur Online-Überwachung mit vielen Schwierigkeiten verbunden. Aufgrund dieser Schwierigkeiten bieten sich für komplexe Systeme qualitative Modellierungsverfahren an. Bei diesen Verfahren müssen die inneren physikalischen Zusammenhänge nicht genau wiedergegeben werden, sondern die Modelle enthalten nur Situationen, in denen etwas „passiert“. Das qualitative Modell muss solche Situationen voneinander unterscheiden können. Eine Möglichkeit, diese Schwierigkeiten in den Griff zu bekommen, ist die Kombination von qualitativen und kontinuierlichen, so genannten hybriden Modellen. Im Rahmen des Forschungsthemas „Entwicklung hybrider Komponentenmodelle zur Prozessüberwachung komplexer dynamischer Systeme“ wurde das SQMD-Verfahren (Situation based Qualitative Monitoring and Diagnosis) entwickelt. Das Verfahren zeichnet sich durch eine einfache, streng komponentenorientierte Modellierung aus. Komponenten ohne Speicherwirkung des technischen Prozesses werden nur qualitativ modelliert. In diesem Fall ordnet der Modellierer jeder physikalischen Größe verschiedene Wertebereiche zu, die das ordnungsgemäße und das fehlerhafte Verhalten dieser Komponente qualitativ beschreiben. Die dynamische Beschreibung erfolgt nur für Komponenten mit Speicherwirkung und wird für die Abbildung des dynamischen Systemverhaltens im qualitativen Modell benötigt. Im Rahmen der Online-Überwachung werden innerhalb eines bestimmten Zeitfensters alle Komponenten miteinander verknüpft und der Zustandsraum reduziert. Dies erfolgt auf Basis der hybriden Komponentenmodelle, der Systemstruktur und der vom technischen Prozess eingehenden Sensor- und Aktordaten. Der reduzierte Zustandsraum kann auf eventuelles Fehlverhalten des technischen Prozesses untersucht werden. Die Durchführbarkeit des Konzepts wird am Modellprozess Drei-Tank-System demonstriert. Anschließend findet die Übertragung auf ein reales System, die Überwachung der aero- und gasdynamischen Prozesse im Kohlebergwerk, statt.Item Open Access The design and implementation of a presentation system for interactive 3D graphics applications(2005) Stegmaier, Simon; Klein, Thomas; Strengert, Magnus; Ertl, ThomasWe present the design and implementation of a stand-alone system for presenting interactive 3D graphics applications and arbitrary multimedia contents to a public audience. The description includes technical details regarding the construction of a sturdy case to accommodate touchscreen, PC, video projector, and sound equipment, and details involved in the design of the presentation software. The presented system was evaluated during a week-long exhibition with several hundreds of users.Item Open Access Reguläre Häufigkeitsberechnungen(2005) Austinat, Holger; Diekert, Volker (Prof. Dr.)Die vorliegende Arbeit beschäftigt sich mit Häufigkeitsberechnungen, einem rekursionstheoretischen Begriff, der in den 60er Jahren von Rose eingeführt wurde. Eine Funktion f ist berechenbar mit Frequenz m/n, wenn es einen Algorithmus gibt, der für je n verschiedene Eingaben n Ausgabewerte berechnet, von denen mindestens m mit den zugehörigen Funktionswerten von f übereinstimmen. Eine erste natürliche Fragestellung war: gibt es nicht-berechenbare Funktionen, die mit einer Frequenz nahe 1 berechnet werden können? Trakhtenbrot beantwortete diese Frage 1963 negativ, indem er zeigte, dass eine Funktion mit Frequenz echt größer als 1/2 bereits berechenbar im herkömmlichen Sinne ist. Andererseits gibt es überabzählbar viele Funktionen, die sich mit Frequenz 1/2 berechnen lassen. Also ist dieses Ergebnis optimal. Die Forschung auf diesem Gebiet intensivierte sich daraufhin: Wissenschaftler wie Dëgtev, Kinber und Trakhtenbrot selbst (in den 70er und 80er Jahren) und Beigel, Gasarch, Hinrichs, Kummer, Stephan, Tantau und Wechsung (ab den 90er Jahren) beschäftigten sich mit verschiedenen Aspekten von Häufigkeitsberechnungen und verwandten Berechenbarkeitsbegriffen. In der vorliegenden Arbeit beschäftigen wir uns vorwiegend mit regulären Häufigkeitsberechnungen, also solchen, die von endlichen Automaten vorgenommen werden können. Kinber untersuchte diesen Aspekt als erster im Jahre 1976 und behauptete, dass sich Trakhtenbrots Resultat auf endliche Automaten überträgt. Sein folgerte dies aus einem allgemeineren Resultats über separierbare Sprachen, das sich allerdings als falsch herausstellte (ein Gegenbeispiel wurde 2002 von Tantau angegeben). (Zwei disjunkte Sprachen A und B heißen separierbar, wenn ein Algorithmus alle Wörter aus A akzeptiert und alle Wörter aus B ablehnt). Die Frage, ob das Analogon von Trakhtenbrots Resultat für endliche Automaten gilt, stellte sich also von neuem. Diese Dissertation enthält folgende Ergebnisse. In Kapitel 2 geben wir zwei Beweise für Trakhtenbrots Resultat an. Zunächst präsentieren wir seinen Originalbeweis, um dann einen neuen kombinatorischen Beweis zu geben, der einen großen Vorteil besitzt: er erlaubt die Übertragung des Ergebnisses auf endliche Automaten. Zwei kleinere Resultate beschließen dieses Kapitel: der Nachweis, dass es überabzählbar viele nicht häufigkeitsberechenbare Sprachen gibt, und eine Darstellung des Zusammenhangs von Häufigkeitsberechnungen und sog. mulit-selektiven Mengen. In Kapitel 3 arbeiten wir den Fehler in Kinbers Beweis über separierbare Sprachen heraus und geben ein konkretes Gegenbeispiel an. Dann untersuchen wir die Separierbarkeit von sog. Pfad- und Anti-Pfadsprachen, die wie folgt definiert sind: sei alpha ein unendliches Wort über dem Alphabet { 0, 1 }; dann ist A(alpha) die Menge der endlichen Präfixe von alpha, und B(alpha) die Menge der Wörter von A(alpha), bei denen das letzte Bit negiert wurde. Wir zeigen, dass A(alpha) und B(alpha) genau dann separiert werden können, wenn die 1-Positionen von alpha berechnet werden können. Andererseits gibt es überabzählbar viele alpha, für die A(alpha) und B(alpha) mit Frequenz 1/2 berechnet werden können. Wenn (ab drei Eingaben) nur ein Fehler zugelassen ist, dann sind A(alpha) und B(alpha) bereits rekursiv. Dieses Ergebnis überträgt sich auch auf endliche Automaten. Zum Abschluss dieses Kapitels zeigen wir, dass sich Kinbers Vermutung (dass Trakhtenbrots Resultat auch für Sprachen gilt, die durch endliche Automaten separiert werden können) nicht retten lässt: für jede Konstante q < 1 gibt es Werte 1 <= m < n mit m/n > q und ein alpha derart, dass A(alpha) und B(alpha) durch endliche Automaten mit Frequenz m/n separiert werden können, jedoch nicht rekursiv separierbar sind. In Kapitel 4 untersuchen wir verschiedene Aspekte regulärer Häufigkeitsberechnungen. Wir zeigen zunächst, dass sich Trakhtenbrots Resultat auf endliche Automaten überträgt, indem wir den neuen Beweis aus Kapitel 2 nochmals genauer betrachten. Anschließend zeigen wir, dass aperiodische Automaten, die Häufigkeitsberechnungen durchführen, nur aperiodische reguläre Sprachen berechnen können (aperiodische Sprachen entsprechen sternfreien Sprachen). Dann beweisen wir ein sog. Iterationskriterium, das vergleichbar mit dem bekannten Pumping-Lemma für reguläre Sprachen ist und uns für viele konkrete Beispielsprachen den Nachweis erlaubt, dass diese nicht häufigkeitsberechenbar sind. Im letzten Teil untersuchen wir dann Abschlusseigenschaften der Klasse der regulär häufigkeitsberechenbaren Sprachen: wir zeigen, dass sie eine boolesche Algebra bilden, jedoch nicht unter Spiegelung abgeschlossen sind. Darüberhinaus ist die Vereinigung zweier Sprachen, die mit Frequenz 1/n erkennbar sind, in der Regel nicht 1/n-erkennbar. Wir beweisen eine untere Schranke, die sehr nah an der besten bekannten oberen Schranke liegt.Item Open Access Laws for rewriting queries containing division operators(2005) Rantzau, Ralf; Mangold, ChristophRelational division, also known as small divide, is a derived operator of the relational algebra that realizes a many-to-one set containment test, where a set is represented as a group of tuples: Small divide discovers which sets in a dividend relation contain all elements of the set stored in a divisor relation. The great divide operator extends small divide by realizing many-to-many set containment tests. It is also similar to the set containment join operator for schemas that are not in first normal form. Neither small nor great divide has been implemented in commercial relational database systems although the operators solve important problems and many efficient algorithms for them exist. We present algebraic laws that allow rewriting expressions containing small or great divide, illustrate their importance for query optimization, and discuss the use of great divide for frequent itemset discovery, an important data mining primitive. A recent theoretic result shows that small divide must be implemented by special purpose algorithms and not be simulated by pure relational algebra expressions to achieve efficiency. Consequently, an efficient implementation requires that the optimizer treats small divide as a first-class operator and possesses powerful algebraic laws for query rewriting.Item Open Access Analysis and verification of systems with dynamically evolving structure(2004) König, Barbara; Esparza, Javier (Prof. Dr.)This thesis is concerned with verification and analysis techniques for software systems characterized by dynamically evolving structure, such as dynamic creation and deletion of objects, mobility and variable topology. Examples for such systems are pointer structures, object-based systems and communication protocols in which the number of participants is not constant. The approach taken here is based on graph transformation systems, an intuitive and---at the same time---powerful formalism for the modelling of distributed and mobile systems. So far there exists comparatively little research concerning the verification of graph rewriting. We will---in the first part of this thesis---introduce graph transformations and give an overview of existing analysis and verification methods, with a focus on the verification of systems with dynamically evolving structure. Then we will describe three original lines of research: behavioural equivalences, type systems and approximation by Petri nets, all of them concerned with the analysis of graph transformation systems. The second part consists of eight refereed research papers treating the previously introduced analysis and verification techniques in depth.