Universität Stuttgart
Permanent URI for this communityhttps://elib.uni-stuttgart.de/handle/11682/1
Browse
Search Results
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 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 Standardisierte Auszeichnungssprachen der Computergraphik für interaktive Systeme(2005) Rotard, Martin; Ertl, Thomas (Prof. Dr.)Computergraphik wird in vielen Bereichen der anwendungsorientierten Informatik, von der optischen Gestaltung graphischer Benutzungsoberflächen bis zur Visualisierung wissenschaftlicher Zusammenhänge eingesetzt. Auszeichnungssprachen zur Beschreibung graphischer Information erweitern diese Einsatzmöglichkeiten um die Animation und die Interaktion mit den Inhalten. In dieser Arbeit werden neue Verfahren und Strategien entwickelt, die den Einsatz von standardisierten Auszeichnungssprachen der Computergraphik in den Bereichen Benutzungsoberflächen und Lehrmaterialien ermöglichen. Dabei liegt ein Schwerpunkt auf der Zugänglichkeit von graphischen Inhalten für blinde Menschen, insbesondere durch interaktive Exploration von taktilen Darstellungen. Diese Arbeit stellt Methoden für die Beschreibung von skalierbaren Interaktionselementen mit Auszeichnungssprachen vor, die an verschiedenste Anzeigegeräte angepasst werden können. Darauf aufbauend entstanden neue Konzepte für zoombare Benutzungsoberflächen zur variablen Größendarstellung von Interaktionselementen und deren Inhalten. Erstmals werden auch Methoden vorgestellt, um die Darstellung von Benutzungsoberflächen, die mit Auszeichnungssprachen beschrieben werden, auf andere Rechner zu übertragen. Der Einsatz von Graphiken, die auf Auszeichnungssprachen basieren, bietet bei deren Erstellung, Handhabung und Anwendung erhebliche Vorteile gegenüber herkömmlicher Rastergraphik. Diese Arbeit stellt neue Verfahren vor, um die Formatierungen von Graphiken in Lehrmodulen anzupassen. Entwickelt werden unter anderem Konzepte für die Generierung von Lehrmodulen, die eine flexible Wiederverwendung in verschiedenen Lernszenarien ermöglichen. Für blinde Menschen bilden textuelle Inhalte die Hauptinformationsquelle bei ihrer Arbeit mit Computersystemen. Die ganzheitliche Darstellung von textuellen und graphischen Inhalten ist für viele Anwendungen jedoch unabdingbar. Mit Graphik, die auf Auszeichnungssprachen basiert, können erstmals Verfahren für die taktile Repräsentation präsentiert werden, die eine ganzheitliche Erschließung der graphischen Inhalte ermöglichen. Dazu werden Methoden vorgestellt, die blinden Menschen den Zugang zu mathematischen Ausdrücken, zu 2D- und zu 3D-Graphiken gestatten. Dies wird an einem taktilen Web-Browser demonstriert, der den Zugang zu diesen unterschiedlichen Graphikarten integriert.Item Open Access Adaptive Internetanbindung von Feldbussystemen(2005) Eberle, Stephan; Göhner, Peter (Prof. Dr.-Ing. Dr. h. c.)Feldbusse sind spezialisierte Netzwerke, um automatisierungstechnische Geräte wie Sensoren, Aktoren und Steuerungen miteinander zu verbinden. In der letzten Zeit wird immer mehr nach Möglichkeiten gesucht, um mit Hilfe des Internets von entfernten Orten aus an Informationen zu gelangen, die in feldbusvernetzten Systemen verarbeitet werden. Die Verfügbarkeit dieser Informationen verleihen Teleservices, wie z.B. der Ferndiagnose, oder der vertikalen Integration automatisierungstechnischer Anlagen mit kaufmännischen Geschäftsbereichen von Unternehmen einen enormen Auftrieb und versprechen Effizienzsteigerungen und Kosteneinsparungen beträchtlichen Ausmaßes. Nichtsdestotrotz erweist sich die fehlende Interoperabilität zwischen Feldbussystemen und darauf zugreifenden Softwarewerkzeugen und -anwendungen nach wie vor als schwer überwindbares Hindernis. Dass zur Beseitigung dieser Schwierigkeiten standardisierte Anwendungsschnittstellen und Datenaustauschformate notwendig sind, darüber ist man sich weitgehend einig. Die Meinungen über deren Gestaltung liegen jedoch weit auseinander und trotz zahlloser Anstrengungen ist keine Einigung absehbar. Mit der adaptiven Internetanbindung von Feldbussystemen wird die Frage der Interoperabilität von Feldbussystemen und -werkzeugen aus einer völlig neuen Richtung angegangen. Nicht der Anwender soll gezwungen sein, sich nach den Begebenheiten des Feldbussystems zu richten. Stattdessen soll die Technik, sprich das Feldbussystem, in die Lage versetzt werden, sich in flexibler Weise an die jeweilige Werkzeuginfrastruktur des Anwenders anzupassen. Die Verwirklichung dieser Idee erfolgt mit Hilfe von Transformationsvorschriften, die an einem bekannten Ort im Internet bereitgestellt werden. Sobald ein Feldbuswerkzeug und -system miteinander in Verbindung treten, werden die zwischen ihnen ausgetauschten Nachrichten mit Hilfe der passenden Transformationsvorschrift übersetzt, sodass sie von der jeweiligen Gegenseite verstanden und ordnungsgemäß verarbeitet werden können. Auf diese Weise kann die Interoperabilität von Feldbussystemen und -werkzeugen erstmals auch dann hergestellt werden, wenn keine einheitliche Form des Informationsaustausches vereinbart werden kann und beide Seiten im herkömmlichen Sinne inkompatibel sind.Item Open Access Ambiguity functions of context-free grammars and languages(2005) Wich, Klaus; Diekert, Volker (Prof. Dr.)This thesis investigates the relationship between the ambiguity functions for context-free grammars and for context-free languages. It also examines which functions are ambiguity functions and how different ambiguity classes relate to each other. The results can be applied to generalise known results on sequential and parallel parsing of context-free grammars. To understand the main results we define some notions briefly: The ambiguity of a word with respect to a context-free grammar is the number of its derivation trees. The ambiguity function of a context-free grammar maps an integer n to the maximal ambiguity of a word whose length is bounded by n. A context-free language L is f-ambiguous if f is the ambiguity function of some context-free grammar generating L and, roughly speaking, no context-free grammar generating L has a substantially lower ambiguity. A function is an inherent ambiguity function if there is an f-ambiguous context-free language. A homomorphism which maps a symbol either to itself or to the empty word is called a projection. A symbol a is called bounded in a language L if there is a constant c such that no word in L has more than c occurrences of the symbol a. A projection is a bounded contraction for a language L if it erases only symbols which are bounded in L. The main results are: 1. The set of ambiguity functions for cycle-free context-free grammars and the set of inherent ambiguity functions coincide. 2. A technical statement which implies the following two facts: 2.1. The class of context-free languages with polynomially bounded ambiguity is the closure of the class of unambiguous context-free languages under bounded contractions. 2.2. Each reduced cycle-free context-free grammar G is either exponentially ambiguous or its ambiguity is bounded by a polynomial which can be computed from G. (2.2. was already part of the authors Diploma thesis, but the new proof yields in many cases a better polynomial (a polynomial with a lower degree), but never a worse polynomial.) 3. For each computable divergent total non-decreasing function f there is a divergent ambiguity function g such that g(n) is lower than or equal to f(n) for each positive integer n. In fact, the same ambiguity functions occur for the generation of rational trace languages over special independence alphabets. (A rational trace language T is generated by a regular (word) language R if T is the set of traces which are represented by the words in R. The ambiguity of a trace t is the number of representatives in R. It is now straightforward to define the ambiguity function for the generation of T by R.) In addition the thesis contains generalisations for known results on sequential and parallel parsing of context-free grammars. In particular, the thesis considers the (sequential) Earley parsing time of context-free grammars with sublinear ambiguity functions (known to exist due to result 3). Moreover it is shown that each reduced context-free grammars with a polynomially bounded ambiguity can be parsed in logarithmic time on a CREW-PRAM. This is an immediate consequence of 2.1. and a known result for the parallel parsing time of unambiguous context-free grammars.Item Open Access Ein umfassendes Umgebungsmodell als Integrationsstrategie für ortsbezogene Daten und Dienste(2005) Nicklas, Daniela; Mitschang, Bernhard (Prof. Dr.)Der ständige Fortschritt in mobilen Computersystemen und Sensortechnologien ermöglicht eine neue Klasse von Anwendungen: sogenannte kontextbezogene Anwendungen passen sich der Situation (dem Kontext) ihres Benutzers in Präsentation, Informationsselektion und Aktion an. Einen wichtigen Hinweis auf die Situation liefert der Ort eines Benutzers, der über heutige Lokalisierungstechniken verhältnismäßig einfach bestimmt werden kann.Wir sprechen von ortsbezogenen Anwendungen, wenn der räumliche Kontext als primäres Selektionskriterium für die Adaption genutzt wird. Solche Anwendungen benötigen ein Datenmodell, das Informationen ortsbezogen referenziert, ein sogenanntes Umgebungsmodell. Dieses enthält alle für die Anwendung relevanten Informationen über ihre Umgebung: sowohl Repräsentationen der physischen Welt wie auch digitale Daten und Dokumente, die über das Umgebungsmodell mit der physischen Welt verknüpft werden. Für eine Vielzahl unterschiedlicher Daten steht durch den Ort ein umfassendes Sortier- und Selektionskriterium zur Verfügung, durch das wir mit der heutigen Informationsflut besser zurecht kommen können vorausgesetzt, wir können diesen Ortsbezug nutzen. Dadurch wird es möglich, ein umfassendes Umgebungsmodell zu entwickeln, das von verschiedenen ortsbezogenen Anwendungen genutzt wird. Dies hat den Vorteil, dass der hohe Aufwand, Umgebungsmodelle zu erheben und nachzuführen, nicht für jede neue Anwendung erneut auftritt. Diese Arbeit konzipiert ein solches umfassendes Umgebungsmodell, mit dem ortsbezogene Daten und Dienste zu einer einheitlichen Sicht integriert werden können. Auch für die Verwaltung des Umgebungsmodells wird in dieser Arbeit eine Lösung vorgestellt. Statt einem monolithischen System aus Datenmodell und Anwendung wird eine Föderationsplattform eingeführt, die Datenanbieter und Anwendungen entkoppelt und dynamisch miteinander verbindet. Dies bietet den Anwendungen verschiedene Transparenzen, in Bezug auf das Schema, den Speicherort, die Systemheterogenität und die Verteilung der Umgebungsmodelldaten. Hierzu wird zunächst eine umfassende Analyse des Anwendungsgebiets ortsbezogener Anwendungen durchgeführt, um inhaltliche Anforderungen an das Umgebungsmodell abzuleiten. Es werden passende Modellierungskonzepte ausgewählt und das Modell aufgebaut. Für die Verwaltung wird eine offene und verteilte Systemplattform entworfen. Die Gesamtlösung wird durch prototypische Implementierung der Plattformkomponenten, Integrationsstudien und die Entwicklung von Beispielanwendungen evaluiert. Insgesamt wird durch diese Arbeit gezeigt, wie durch Ausnutzung domänenspezifischer Eigenschaften (hier: die räumliche Struktur der Daten) eine effiziente, skalierbare und erweiterbare Föderationsarchitektur bereit gestellt werden kann, die über autonome und wechselnde Anbieter hinweg verschiedenen Anwendungen eine integrierte Datensicht bietet.