05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6

Browse

Filters

200421

Settings

Start date: 2004End date: 2004

Search Results

Now showing 1 - 10 of 21
  • Thumbnail Image
    ItemOpen Access
    Deriving bisimulation congruences in the DPO approach to graph rewriting. Long version
    (2004) Ehrig, Hartmut; König, Barbara
    Motivated 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.
  • Thumbnail Image
    ItemOpen 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.
  • Thumbnail Image
    ItemOpen 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.
  • Thumbnail Image
    ItemOpen 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.
  • Thumbnail Image
    ItemOpen 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.
  • Thumbnail Image
    ItemOpen Access
    Complexity results for checking distributed implementability
    (2004) Heljanko, Keijo; Stefanescu, Alin
    We consider the distributed implementability problem as: Given a labelled transition system TS together with a distribution D of its actions over a set of processes, does there exist a distributed system over D such that its global transition system is equivalent' to TS? We consider the distributed system models of synchronous products of transition systems and Zielonka's asynchronous automata. In this paper we provide complexity bounds for the above problem with three interpretations of equivalent': as transition system isomorphism, as language equivalence, and as bisimilarity. In particular, we solve two problems left open in the literature. We also describe a logic programming implementation which complements the existing implementation for the synthesis of asynchronous automata initiated by the second author.
  • Thumbnail Image
    ItemOpen Access
    Hierarchical methods for filtering and visualization based on graphics hardware
    (2004) Hopf, Matthias; Ertl, Thomas (Prof. Dr.)
    Interactive visualization of large data sets is only possible with efficient algorithms for all parts of the visualization pipeline. This thesis analyzes the filtering and the rendering steps of this pipeline for several fundamentally different data types. Two key techniques that are employed throughout this work are the use of hierarchical methods and graphics-hardware-based implementations of the presented algorithms. In order to improve the efficiency of filtering, both linear and nonlinear filters are accelerated using graphics hardware for the computation. For many algorithms hierarchical filters based on wavelets are needed and, therefore, inspected as well. Finally, the quality of the achieved results is analyzed, as the accuracy of graphics-card-based approaches is limited by register sizes and framebuffer depths. During rendering hierarchical approaches allow for a compact representation of partially detailed data. Additionally, the user can trade visualization speed for quality. Sparse grids allow for extremely compact representations, thus interpolated data from sparse grids would no longer fit into main memory. This raises the need for visualization algorithms working directly on the sparse grid coefficients. The interpolation process is expensive, but graphics hardware is usually too inaccurate to be used for acceleration. Thus, the rendering process is parallelized with MPI, using a ray distribution scheme that implicitly generates previews with lower resolution during rendering. For unstructured data a compact hierarchical representation with radial basis functions is introduced that can be employed for rendering at interactive frame rates using graphics hardware. Completely uncorrelated data like astrophysical n-body problems have high spatial resolution which is lost during resampling for volume rendering. A new hierarchical splatting approach is presented that is able to visualize tens of millions of points interactively for steady and time-dependent data sets. The used data representations have different approximation capabilities, thus the properties of the different data encodings are analyzed by comparing several data sets that exhibit different amounts of features.
  • Thumbnail Image
    ItemOpen Access
    A note on on-the-fly verification algorithms
    (2004) Schwoon, Stefan; Esparza, Javier
    The automata-theoretic approach to verification of LTL relies on an algorithm for finding accepting cycles in the product of the system and a Büchi automaton for the negation of the formula. Explicit-state model checkers typically construct the product space "on the fly" and explore the states using depth-first search. We survey algorithms proposed for this purpose and propose two improved algorithms, one based on nested DFS, the other on strongly connected components. We compare these algorithms both theoretically and experimentally and determine cases where both algorithms can be useful.
  • Thumbnail Image
    ItemOpen Access
    Sprachwissenschaft: Eine Wissenschaft?
    (2004) Kamp, Hans
    Die Linguistik gehört zu den "Sciences de l'Homme" – den Wissenschaften, die unsere eigene Spezies, die des Homo Sapiens, betreffen – und insbesondere diejenigen Aspekte, die den Menschen innerhalb der Menge aller Lebewesen als das Einzigartige auszeichnen, für das wir uns halten. Diese Aspekte haben immer etwas mit dem menschlichen "Geist" zu tun oder mit der kognitiven Veranlagung des Menschen, wenn man eine solche Formulierung vorzieht, und mit dem Gebrauch, den er von dieser Veranlagung macht. Dies gilt insbesondere auch für den Gegenstandsbereich der Linguistik: die menschlichen Sprachen und unsere Fähigkeit, sie zu erwerben und zu verwenden. Die Linguistik ist nicht die einzige Wissenschaft, die die Sprache zum Gegenstand hat. In vielen anderen "Sciences de l'Homme" spielt sie ebenfalls eine wichtige oder sogar zentrale Rolle. In manchen, wie zum Beispiel in der Literaturwissenschaft, geht es sogar - ebenso wie in der Linguistik - ausschließlich um Sprache.
  • Thumbnail Image
    ItemOpen Access
    Event management for mobile users
    (2004) Bauer, Martin
    This technical report presents the results of the project "Event Management for Mobile Users", a research cooperation between Universität Stuttgart and Microsoft. In Vienna, Microsoft chief executive Bill Gates recently expressed his vision of a seamless interaction of different computing devices, from PC to mobile phone, that proactively support the users wherever they go. Among other things, he said: "For example, if you want to be notified about something that's changing, that's important to you, software should know which device you have with you and should know what you're doing, know the context to understand if interrupting you with this new information is appropriate or not." (Bill Gates, January 28, 2004, [Los Angeles Times 2004]) This project may present one step towards realizing his vision. It is about event support for mobile users. Depending on their current context, they want to be informed about events that occur in the world around them - the physical as well as the virtual world of digital information systems. So, to optimally support its users, future generations of web services will need information about the real-world context of the user, especially their spatial context. This project was carried out in close cooperation with the Nexus project at Universität Stuttgart, whose goal is to support mobile context-aware applications based on a distributed spatial world model. Events of special interest in this context are spatial events, i.e. events that occur when a certain spatial constellation of objects is reached, e.g. when two people meet or when a customer enters a shopping mall. As the underlying world model is distributed, the events have to be observed on a distributed model. The number of potential spatial events is not restricted, e.g. the event that a user enters an area could be of interest for arbitrary areas. Also, as the spatial world model is distributed over many servers, a local observation is no longer sufficient. Therefore, the well-known publish-subscribe paradigm, in which the observation occurs implicitly within local observers, has to be extended. We propose an observation-notification paradigm, in which the observation of events has to be explicitly initiated by interested clients. The event service that conforms to the new paradigm consists of two components: an observation service, which observes events through a distributed model, and a notification service, which efficiently delivers event notifications. This paradigm applies to all scenarios in which the data needed for the observation of events is distributed over multiple sources. The user wants the specification of events to be as simple and easy as possible. He only wants to specify what event is to be observed, not how the observation of the event is realized. Therefore the distribution aspects should be transparent to the user. However, these aspects have a strong influence on the accuracy of the model and thereby directly affect the accuracy of event observation. We propose that the user specifies an event as a predicate, which becomes true when the event has occurred, plus a threshold probability. If the probability that the event has occurred is above the threshold probability, the event is considered to have occurred and an event notification is sent. The above sketched solution requires calculating the probability with which an event has occurred. We first show which parameters influence the accuracy of the data. We then present update protocols that guarantee a certain accuracy of data in the observer model, i.e. the model where the event is actually observed. Finally we show, how the occurrence probability can be calculated. Based on the identified parameters, the placement of the observation in the system can also be optimized with regard to the accuracy of the data. We have implemented the event service and integrated it into the Nexus platform. As the Nexus platform is intended as an open platform with possibly world-wide scale, scalability, efficiency and interoperability have been important requirements for the design of the components. To support interoperability, we have built on standard technologies like XML, HTTP and SOAP. The evaluation of the event service within the Nexus context shows the feasibility of the approach. We were able to show that the event service performs adequately in certain example scenarios. Experiments with a large-scale scenario are the next steps on our agenda.