In der vorliegenden Arbeit werden praktische Protokolle für spontane drahtlose Multi-Hop Maschennetze vorgestellt, diese betrachten das drahtlose System ganzheitlich und berücksichtigen damit die Besonderheiten des drahtlosen Mediums, wie Fading, Interferenz sowie starke Signaldämpfung aufgrund von Entfernung bzw. Hindernissen. Interferenz ist eine Hauptursache für Paketverlust, Durchsatz und Latenz können durch die gleichzeitige Verwendung mehrerer interferenzfreier Kanäle verbessert werden. In Sensor- bzw. Community-Netzen kommt preiswerte und energiesparende Hardware zum Einsatz, die Verwendung zusätzlicher Antennen bzw. Radios ist deshalb nicht möglich. Andererseits werden aber zukünftige drahtlose Netze eine 100-mal höhere Knotendichte, verglichen mit heutigen Netzen, zeigen. Durch die Ausnutzung der im System inhärent vorliegenden Ressource Nutzer (Multi-User Diversität) werden durch Kooperation virtuelle Multi-Antennen und Multi-Radiosysteme aufgebaut. Aufgrund des großen Abstands zwischen den Knoten erreicht man erstens eine hohe räumliche Diversität und zweitens lassen sich damit auch negative Effekte, wie Interferenz zwischen benachbarten Kanälen, minimieren. Es werden Algorithmen sowohl für die Mediumzugriff- als auch die Routing-Schicht vorgestellt. Da keine spezielle physikalische Schicht notwendig ist, kann IEEE 802.11 verwendet werden. Schließlich kann auch auf die bereits heute verfügbare IEEE 802.11 Hardware, die nur eine Kanalumschaltzeit im Millisekundenbereich erlaubt, zurückgegriffen werden. Die zwei vorgestellten Protokolle eignen sich für Umgebungen mit hoher bzw. geringer Interferenz durch fremde WiFi-Netze. Bezüglich Durchsatz werden moderne Protokolle, wie DSR auf Basis von IEEE 802.11 und ETX-Metrik, um ein Vielfaches übertroffen, außerdem ist die Latenz klein und das TCP/IP-Protokoll kann unverändert verwendet werden. / In this work practical protocols are introduced for spontaneous wireless multi-hop mesh networks which contemplate the wireless system integrally and therefore take into account particular features of the wireless medium, like fading, interference as well as strong signal attenuation due to distance or obstacles. Interference is one of the main causes for packet loss. Throughput and latency can be improved by the simultaneous use of several non-interfering channels. In sensor or community networks inexpensive and energy-saving hardware is used. Additional antennas or radios are impossible therefore; on the other hand future wireless networks will show a 100 times higher node density in comparison with today''s networks, however. By the usage of the resource user (multi-user diversity), that is inherently present in the system virtual multi-antennas and multi-radio systems can be built up by cooperation. Firstly, a high spatial diversity can be achieved due to the large distance between the nodes and secondly, negative effects like interference can be minimized between neighboring channels. Algorithms are introduced both for medium access and routing layer. Since a special physical layer is not required IEEE 802.11 can be used. These days already available 802.11 hardware, which allows a channel switching time in milliseconds, is finally usable. The two protocols introduced here are suitable for environments with a high or low interference caused by foreign WiFi networks. Regarding their performance modern protocols like DSR based on 802.11 and ETX metric are surpassed by far. Moreover, the latency is small and the TCP/IP protocol can be used in its unchanged form.

Selbstorganisierte drahtlose (ad hoc) Multihopnetzwerke können als einfach einsetzbare, robuste und rekonfigurierbare Kommunikationsinfrastruktur zum Beispiel in Katastrophenszenarien eingesetzt werden. Solche drahtlosen Netzwerke nutzen die Luft als geteiltes Kommunikationsmedium, was bedeutet, dass die Parameter des Netzwerks sehr orts- und zeitveränderlich sowie verrauscht sind. Intelligente Roboter können als Netzwerkknoten diese Herausforderungen bewältigen, indem sie sensomotorische Interaktion ausnutzen. Für einzelne Roboter wurde ein Algorithmus zur Exploration unbekannter Netzwerke entwickelt. Außerdem wurde gezeigt, dass eine Klasse gradientenbasierter Navigationsalgorithmen für den Fall von Signalstärkemessungen konvergiert. Es wurde zudem gezeigt wie diese Art von Algorithmen sich auf andere Aufgaben als das Finden von Netzwerkknoten erweitern lassen. Zusätzlich wurde ein Algorithmus basierend auf internen Modellen, der dem Roboter zum Beispiel ermöglicht Netzwekknoten finden oder zwei Netzwerkknoten zu überbrücken, entwickelt. Alle Algorithmen wurden in Simulation oder mit echten Robotern implementiert und evaluiert. Für den Fall mehrerer Roboter existieren bereits viele interessante Algorithmen in der Literatur. Allerdings wird im Moment keiner dieser Algorithmen in realen Systemen eingesetzt. Einer der Gründe hierfür ist, dass naive Sachwarmalgorithmen meist nicht sicher und zuverlässig genug sind. Um dieses Problem zu lösen wurde eine Architektur, die auf internen Modellen basiert und interne Simulation nutzt, untersucht. Es wurden zwei Testszenarien analysiert: Im ersten Experiment sollte ein Roboter andere Roboter davor bewahren zu Schaden zu kommen und dabei gleichzeitig seine eigene Sicherheit gewährleisten und eine Aufgabe erfüllen. Im zweiten Experiment musste ein Roboter durch einen Korridor navigieren ohne mit anderen Robotern zusammenzustoßen. Die vorgeschlagene Architektur hat sich als sehr effektiv erwiesen. / Self-organized wireless multihop (ad hoc) networks can form an easily deployable, robust and reconfigurable communication infrastructure, which can be employed for example in a disaster scenario, when static communication infrastructure has been destroyed. As such wireless networks use the air as a shared physical medium, the parameters of these networks often show very space- and time-varying noisy characteristics. Intelligent robotic network nodes can overcome these problems posed by these dynamics and measurement noise by exploiting sensorimotor interaction. For single robots, an algorithm for network exploration of unknown networks for large scale outdoor scenarios has been developed. Furthermore, a class of gradient-based algorithms for navigation in wireless networs hase been shown to converge for the case of signal strength measurements. Additionally, it was shown how these algorithms can be extended to other tasks than locating a network node. Additionally, an internal model-based algorithm to solve tasks like locating a node or bridging two nodes has been developed. All algorithms have been implemented and evaluated either in simulation or on real robots. For the case of multiple robots, a lot of interesting algorithms for example for optimal placement of mobile network nodes have been presented in literature. However, none of them are being used in real world scenarios. One of the reasons for that is insufficient safety and fault tolerance of naive algorithms. To overcome this problem the use of an internal model-based architecture using internal simulation has been investigated. Two test scenarios have been investigated using this architecture: in the first experiment a robot had to prevent other robots from coming to harm while ensuring its own safety and fulfilling a task. In a second experiment, a robot had to navigate through a narrow corridor without colliding with other robots. The proposed architecture has been shown to be very effective.

Metamodellierung im Sinne der Meta Object Facility (MOF) stellt eine Methode für die strukturelle Definition der abstrakten Syntax von Modellierungssprachen und Modellen im Softwareentwicklungsprozess dar. Um Modellsimulation und dynamische Analysen für metamodellbasierte Sprachen zu unterstützen, fehlt es an einem Kalkül zur operationalen Semantik. In dieser Arbeit wird ausgehend von MOF die Aktionssemantik MActions entwickelt, die die Definition von operationaler Semantik als Verhalten in Metamodellen ermöglicht. Diese Erweiterung geht einher mit der Beschreibung von Laufzeitmodellen sowie Zuständen und Parallelitätseigenschaften, so dass eine Verifikation von dynamischen Eigenschaften möglich wird. Zu diesem Zweck wird mit der Linear Temporal Object Constraint Language (LT-OCL) exemplarisch eine prädikatenlogische Temporallogik entwickelt, die eine metamodellunabhängige Analyse für ausführbare Modelle erlaubt. Dabei ist die Semantik von temporalen Ausdrücken über Zuständsänderungen von (aufgezeichneten) Ausführungsläufen beschrieben, wobei eine Linearisierung parallele Änderungen zusammenführt. Als weiteren Anwendungsfall der dynamischen Analyse untersuchen wir die Relation zum Verhaltensvergleich im Sinne der Bisimulationstheorie. Metamodelle, Aktionssemantik und Temporallogik werden mittels einer erweiterten Abstract State Machine (ASM) formal beschrieben und kommen in zwei Fallstudien zur Anwendung (Timed Automata und C#). / Object-oriented metamodelling as defined by the Meta Object Facility (MOF) provide a means to describe the structure of models and the abstract syntax of modelling languages at various stages in a software development process. However, MOF lacks concepts for the definition of operational semantics and there is no support for dynamic model analysis based on the semantics and abstract states of a language definition. This thesis investigates on extending the metamodelling framework with an action semantics - the MActions - to support the definition of operational semantics in metamodels and enable simulation as well as verification of dynamic properties. For this purpose, runtime models are incorporated with semantics for states, time, and properties of parallelism that allow a generic analysis solely bound to a certain metamodel definition. Furthermore, we develop the Linear Temporal Object Constraint Language (LT-OCL) to perform a dynamic analysis of execution runs based on the executable models. The semantics of this temporal predicate logic is bound to state changes of (recorded) execution traces that are linearizations of parallel changes of the runtimes model. This establishes the link to the theory of bisimulation as a second application case of dynamic analysis. Abstract State Machines (ASM) have been used to formally define the action language in conjunction with metamodels and the temporal logic. As proof of concept of the whole approach, the framework has been implemented and applied to two languages as case studies (namely Timed Automata and C#).

Mit der vorliegenden Dissertation soll ein Beitrag zur Steigerung der Genauigkeit und Zuverlässigkeit einer sensorgestützten Objekterkennung im Fahrzeugumfeld geleistet werden. Aufbauend auf einem Erfassungssystem, bestehend aus einer Stereokamera und einem Mehrzeilen-Laserscanner, werden teils neu entwickelte Verfahren für die gesamte Verarbeitungskette vorgestellt. Zusätzlich wird ein neuartiges Framework zur Fusion heterogener Sensordaten eingeführt, welches über eine Zusammenführung der Fusionsergebnisse aus den unterschiedlichen Verarbeitungsebenen in der Lage ist, die Objektbestimmung zu verbessern. Nach einer Beschreibung des verwendeten Sensoraufbaus werden die entwickelten Verfahren zur Kalibrierung des Sensorpaares vorgestellt. Bei der Segmentierung der räumlichen Punktdaten werden bestehende Verfahren durch die Einbeziehung von Messgenauigkeit und Messspezifik des Sensors erweitert. In der anschließenden Objektverfolgung wird neben einem neuartigen berechnungsoptimierten Ansatz zur Objektassoziierung ein Modell zur adaptiven Referenzpunktbestimmung und –Verfolgung beschrieben. Durch das vorgestellte Fusions-Framework ist es möglich, die Sensordaten wahlweise auf drei unterschiedlichen Verarbeitungsebenen (Punkt-, Objekt- und Track-Ebene) zu vereinen. Hierzu wird ein sensorunabhängiger Ansatz zur Fusion der Punktdaten dargelegt, der im Vergleich zu den anderen Fusionsebenen und den Einzelsensoren die genaueste Objektbeschreibung liefert. Für die oberen Fusionsebenen wurden unter Ausnutzung der konkurrierenden Sensorinformationen neuartige Verfahren zur Bestimmung und Reduzierung der Detektions- und Verarbeitungsfehler entwickelt. Abschließend wird beschrieben, wie die fehlerreduzierenden Verfahren der oberen Fusionsebenen mit der optimalen Objektbeschreibung der unteren Fusionsebene für eine optimale Objektbestimmung zusammengeführt werden können. Die Effektivität der entwickelten Verfahren wurde durch Simulation oder in realen Messszenarien überprüft. / With the present thesis a contribution to the increase of the accuracy and reliability of a sensor-supported recognition and tracking of objects in a vehicle’s surroundings should be made. Based on a detection system, consisting of a stereo camera and a laser scanner, novel developed procedures are introduced for the whole processing chain of the sensor data. In addition, a new framework is introduced for the fusion of heterogeneous sensor data. By combining the data fusion results from the different processing levels the object detection can be improved. After a short description of the used sensor setup the developed procedures for the calibration and mutual orientation are introduced. With the segmentation of the spatial point data existing procedures are extended by the inclusion of measuring accuracy and specificity of the sensor. In the subsequent object tracking a new computation-optimized approach for the association of the related object hypotheses is presented. In addition, a model for a dynamic determination and tracking of an object reference point is described which exceeds the classical tracking of the object center in the track accuracy. By the introduced fusion framework it is possible to merge the sensor data at three different processing levels (point, object and track level). A sensor independent approach for the low fusion of point data is demonstrated which delivers the most precise object description in comparison to the other fusion levels and the single sensors. For the higher fusion levels new procedures were developed to discover and clean up the detection and processing mistakes benefiting from the competing sensor information. Finally it is described how the fusion results of the upper and lower levels can be brought together for an ideal object description. The effectiveness of the newly developed methods was checked either by simulation or in real measurement scenarios.

Für mobile autonome Roboter ist ein solides Modell der Umwelt eine wichtige Voraussetzung um die richtigen Entscheidungen zu treffen. Die gängigen existierenden Verfahren zur Weltmodellierung basieren auf dem Bayes-Filter und verarbeiten Informationen mit Hidden Markov Modellen. Dabei wird der geschätzte Zustand der Welt (Belief) iterativ aktualisiert, indem abwechselnd Sensordaten und das Wissen über die ausgeführten Aktionen des Roboters integriert werden; alle Informationen aus der Vergangenheit sind im Belief integriert. Wenn Sensordaten nur einen geringen Informationsgehalt haben, wie zum Beispiel Peilungsmessungen, kommen sowohl parametrische Filter (z.B. Kalman-Filter) als auch nicht-parametrische Filter (z.B. Partikel-Filter) schnell an ihre Grenzen. Das Problem ist dabei die Repräsentation des Beliefs. Es kann zum Beispiel sein, dass die gaußschen Modelle beim Kalman-Filter nicht ausreichen oder Partikel-Filter so viele Partikel benötigen, dass die Rechendauer zu groß wird. In dieser Dissertation stelle ich ein neues Verfahren zur Weltmodellierung vor, das Informationen nicht sofort integriert, sondern erst bei Bedarf kombiniert. Das Verfahren wird exemplarisch auf verschiedene Anwendungsfälle aus dem RoboCup (autonome Roboter spielen Fußball) angewendet. Es wird gezeigt, wie vierbeinige und humanoide Roboter ihre Position und Ausrichtung auf einem Spielfeld sehr präzise bestimmen können. Grundlage für die Lokalisierung sind bildbasierte Peilungsmessungen zu Objekten. Für die Roboter-Ausrichtung sind dabei Feldlinien eine wichtige Informationsquelle. In dieser Dissertation wird ein Verfahren zur Erkennung von Feldlinien in Kamerabildern vorgestellt, das ohne Kalibrierung auskommt und sehr gute Resultate liefert, auch wenn es starke Schatten und Verdeckungen im Bild gibt. / For autonomous mobile robots, a solid world model is an important prerequisite for decision making. Current state estimation techniques are based on Hidden Markov Models and Bayesian filtering. These methods estimate the state of the world (belief) in an iterative manner. Data obtained from perceptions and actions is accumulated in the belief which can be represented parametrically (like in Kalman filters) or non-parametrically (like in particle filters). When the sensor''s information gain is low, as in the case of bearing-only measurements, the representation of the belief can be challenging. For instance, a Kalman filter''s Gaussian models might not be sufficient or a particle filter might need an unreasonable number of particles. In this thesis, I introduce a new state estimation method which doesn''t accumulate information in a belief. Instead, perceptions and actions are stored in a memory. Based on this, the state is calculated when needed. The system has a particular advantage when processing sparse information. This thesis presents how the memory-based technique can be applied to examples from RoboCup (autonomous robots play soccer). In experiments, it is shown how four-legged and humanoid robots can localize themselves very precisely on a soccer field. The localization is based on bearings to objects obtained from digital images. This thesis presents a new technique to recognize field lines which doesn''t need any pre-run calibration and also works when the field lines are partly concealed and affected by shadows.

In den letzten Jahren wurden viele Methoden entwickelt, um den Schutz der Privatsphäre bei der Veröffentlichung von Daten zu gewährleisten. Die meisten Verfahren anonymisieren eine gesamte Datentabelle, sodass sensible Werte einzelnen Individuen nicht mehr eindeutig zugeordnet werden können. Deren Privatsphäre gilt als ausreichend geschützt, wenn eine Menge von mindestens k sensiblen Werten existiert, aus der potentielle Angreifer den tatsächlichen Wert nicht herausfinden können. Ausgangspunkt für die vorliegende Arbeit ist eine Sequenz von Anfragen auf personenbezogene Daten, die durch ein Datenbankmanagementsystem mit der Rückgabe einer Menge von Tupeln beantwortet werden. Das Ziel besteht darin herauszufinden, ob Angreifer durch die Kenntnis aller Ergebnisse in der Lage sind, Individuen eindeutig ihre sensiblen Werte zuzuordnen, selbst wenn alle Ergebnismengen anonymisiert sind. Bisher sind Verfahren nur für aggregierte Anfragen wie Summen- oder Durchschnittsbildung bekannt. Daher werden in dieser Arbeit Ansätze entwickelt, die den Schutz auch für beliebige Anfragen gewährleisten. Es wird gezeigt, dass die Lösungsansätze auf Matchingprobleme in speziellen Graphen zurückgeführt werden können. Allerdings ist das Bestimmen größter Matchings in diesen Graphen NP-vollständig. Aus diesem Grund werden Approximationsalgorithmen vorgestellt, die in Polynomialzeit eine Teilmenge aller Matchings konstruieren, ohne die Privatsphäre zu kompromittieren. / Over the last ten years many techniques for privacy-preserving data publishing have been proposed. Most of them anonymize a complete data table such that sensitive values cannot clearly be assigned to individuals. Their privacy is considered to be adequately protected, if an adversary cannot discover the actual value from a given set of at least k values. For this thesis we assume that users interact with a data base by issuing a sequence of queries against one table. The system returns a sequence of results that contains sensitive values. The goal of this thesis is to check if adversaries are able to link uniquely sensitive values to individuals despite anonymized result sets. So far, there exist algorithms to prevent deanonymization for aggregate queries. Our novel approach prevents deanonymization for arbitrary queries. We show that our approach can be transformed to matching problems in special graphs. However, finding maximum matchings in these graphs is NP-complete. Therefore, we develop several approximation algorithms, which compute specific matchings in polynomial time, that still maintaining privacy.

Die erweiterte CSP-CASL Syntax wird dazu verwendet, sowohl positive als auch negative Testfälle zu generieren. Auf diese Weise wird sichergestellt, dass erwartetes und unerwünschtes Verhalten in den Testfäallen enthalten ist. Ferner werden Testterminologien für die CSP-CASL Spezifikation beschrieben, welche Softwareverfeinerungen und Erweiterungen untersuchen. Anschliessend wird die formale Definition von Softwareeigenschaften verwendet, um die Wiederverwendbarkeit von Testbestandteilen zu überprüfen. Diese Definitionen beschreiben die grundlegenden Eigenschaften im vorgeschlagenen Produkt und Prozessqualitäts- Framework. Ferner wird die Möglichkeit untersucht, die vorgeschlagenen Formalismus für die Entwicklung eines CMMI Prozesskonformen Frameworks zu verwenden. Dabei werden die Kernaspekte des CMMI Prozessmodells berücksichtigt. Das CMMI Compliance Bewertungssystem wurde entwickelt, um den Grad der Konformit ät der eingesetzten Softwareentwicklungsmethoden mit formalen Methoden zu bewerten. Ein generischer Algorithmus wird vorgeschlagen, um das Compliance Level der CMMI Prozessfelder und ihrer Komponenten zu ermitteln. Das Framework wird durch ein Tool unterstützt. Dieses Tool erlaubt es, die theoretischen Aspekte der vorgeschlagenen Theoreme praktisch zu unterstützen. Die Verwendbarkeit des vorgeschlagenen Frameworks wird an einem Anwendungsbeispiel aus der Medizintechnik gezeigt. Im Rahmen dieser Arbeit wird das Verständnis der Anwendung von formalen Methoden auf das Organisatorische Prozessmodell CMMI erweitert. Das komplette Framework wird repräsentiert durch die formale Spezifikationssprache CSP- CASL sowie der Prozessmodell CMMI. Ähnliche Ergebnisse können auch mit anderen formalen Methoden und Prozessverbesserungsmodellen erzielt werden. Diese Forschungsarbeit dagegen bildet einen Startpunkt für eine Prozessmodellkonformit ät mit einen auf formalen Methoden basierenden Softwaresystems sowie deren Entwicklung und Wartung. / The proposed formalisms and the other properties of formal methods are used to propose a framework of CMMI process model compliance. The core aspects of the CMMI process model are the process areas. A process area is a collection of best practices in a selected area. The CMMI compliance grading scheme is developed to evaluate the level of compliance with formal method based software development. A compliance algorithm is proposed to evaluate the process model through the evaluation of its components. The CMMI process areas are evaluated with a proposed algorithm. The compliance evaluation result is presented in the thesis. The complete framework is supported with a developed tool. This tool allows us to practically support our theoretical concepts. As a proof of concept, we explore our proposed framework for a medical instrument development and maintenance. In this thesis, the understanding of formal methods applicability is extended to the organizational process model, CMMI. The complete framework is presented for a formal specification language, CSP-CASL and process model, CMMI. However, similar result can be achieved with other formal methods for the compliance of other process models. This research is a starting point of process model compliance with formal methods. This has significant potential to automate the achievement of process and product quality goals of software systems.

Wir befinden uns mitten im Langzeitprojekt »Aufklärung«, dem Ausgang der Menschheit aus ihrer selbstverschuldeten Unmündigkeit – und bislang sieht es gut aus: Die Freiheit der Andersdenkenden, die Gleichheit aller vor dem Gesetz und die Solidarität unter den Menschen auf dem Erdball sind allgemein akzeptierte Entwicklungsziele. Über den Weg dahin lässt sich trefflich streiten, am besten in einer der schwatzhaftesten Staatsformen, eben in der parlamentarischen Demokratie. Der Aushandlungsprozess wird medienöffentlich geführt, von Kants Leserwelt bis zum world wide web von Berners-Lee nutzt der politische Mensch die Kulturtechniken Schrift, Bild und Zahl, um öffentlich von seiner Vernunft Gebrauch zu machen. Informatik ist die technische Wissenschaft, die sich mit dem Entwurf von informations- und kommunikationstechnischen Artefakten und deren Auswirkungen auf die Lebenswelt des Menschen beschäftigt, diese Arbeit fokussiert die technischen Bedingungen der Möglichkeit des öffentlichen Vernunftgebrauchs. Unter Technik soll in dieser Arbeit nicht nur die Gesamtheit der technischen Artefakte oder Systeme verstanden werden, sondern auch Handwerk, Handwerkskunst und sogar Geisteshaltungen, Gedankenketten sowie Algorithmen – ganz wie es die Etymologie des griechischen Wortes τέχνη verrät. Die vorliegende Untersuchung einer technē der Publizität führt uns von der antiken Agora über die aufklärerischen Salons bis zu den virtuellen und realen Orten der Netzöffentlichkeit. Technisch Handelnde besitzen eine ungeheure Macht, die öffentliche Deliberation zu ermöglichen oder zu bremsen. In der nun ausgerufenen Turing-Galaxis muss nun gerade die Informatik in allen Bindestrich-Varianten Verantwortung für die Gewährleistung von Öffentlichkeit übernehmen. Diese Arbeit soll dazu beitragen. / The long term project »Enlightenment« is in full swing: the freedom to dissent, equality under public law, and solidarity with all the people from all over the world – these self-imposed development goals are widely accepted by all human beings. Since everything is exquisitely debated in a parliamentary democracy, this chatty form of government, citizens will of course exquisitely debate on how to achieve these goals. The negotiation process is conducted in and by public media, from Kant''s world of readers (»Leserwelt«) on to the hypermedia of the world wide web, the homo politicus uses cultural techniques like writing, image and number for his public display of reasoning. Informatics (and also computer science for that matter) is the study of designing information and communications technology and assessing it in all social respects; this dissertation focuses on the necessary conditions for the possibility of public reasoning. The Greek word τέχνη is translated as either craft or art, in this political context technē also means mindset, chain of ideas or algorithms. In this enquiry entitled »technē der Publizität«, we will visit places of the public, starting from the Greek »agora« via Victorian coffee houses to the contemporary locations of the networked public sphere. Technicians yield the power to enable or suppress public deliberation; in the so called Turing Galaxy, Informaticians have the responsibility to ensure the possibilities of the existence of an informed public. This thesis tries to accept this responsibility.

In dieser Habilitationsschrift wird die formale Semantik der standardisierten Spezifikationssprache SDL (Specification and Description Language) beschrieben. Da SDL eine sehr umfangreiche Sprache ist, wurde eine repräsentative eingeschränkte Sprache RSDL (Restricted SDL) ausgewählt, um die Konzepte der formalen Definition von SDL darzustellen. Die vorliegende Habilitationsschrift umfaßt zwei große Teile: die Definition der formalen Semantik von RSDL und ihre Implementierung. Die formale Definition der Semantik von RSDL ist verständlich, leicht mit der informalen Beschreibung zu vergleichen und repräsentiert die grundsätzliche Vorstellung von RSDL. Für die Beschreibung werden zwei Teile unterschieden, nämlich die statische Semantik und die dynamische Semantik. Die statische formale Sprachdefinition besteht aus einer konkreten Syntax, einer Menge von Korrektheitsbedingungen, einer Menge von Transformationsregeln und einer abstrakten Syntax als Basis für die dynamische Semantik. Das Ergebnis der statischen Beschreibung ist eine Repräsentation der Spezifikation in abstrakter Syntax. Die Formalisierung der dynamischen Semantik beginnt mit der abstrakten Syntax. Aus dieser abstrakten Syntax wird ein Verhaltensmodell abgeleitet, das auf der mathematischen Theorie der Abstrakten Zustandmaschinen ASM (Abstract State Machines) basiert. Um die Definition der Semantik besonders übersichtlich zu gestalten, wird eine Spezielle Abstrakte Maschine (SAM) unter Nutzung von ASM definiert. Diese abstrakte Maschine stellt eine abstrakte SDL-Maschine dar. Die formale Semantik beschreibt die Eigenschaften von SDL exakt. Um jedoch herauszufinden, ob die Semantik korrekt ist, muß sie mit der Sprachbeschreibung und den Intentionen der Sprachentwickler verglichen werden. Dies geschieht am einfachsten durch eine korrekte Implementierung der Semantik. Die Implementierung der formalen Semantik basiert auf einer Repräsentation der Eingabe als abstrakter Syntaxbaum. Um die Semantik mit minimalem Aufwand zu implementieren, werden existierende Werkzeuge verwendet. Der Compiler wird mit den Standardwerkzeugen lex und yacc generiert. Nach der Syntaxanalyse wird die weitere Verarbeitung über dem abstrakten Syntaxbaum der Eingabe definiert. Die Verarbeitung von abstrakten Syntaxbäumen wird durch ein Werkzeug namens kimwitu erledigt. Mit der hier vorgestellten Technologie wurde die formale Semantik von RSDL implementiert. Entsprechend wird die formale Semantik von SDL implementiert. / In this habilitation thesis the formal semantics of the standardised specification language SDL (Specification and Description Language) is described. Because of the size of the language SDL a representative subset of the language called RSDL (Restricted SDL) was selected to present the concepts of the formal definition. In this thesis two major parts are covered: the definition of the formal semantics and its implementation. The RSDL formal semantics is intelligible, easily comparable with the informal description and represents the general understanding of RSDL. We distinguish between two phases of the definition, namely the static semantics and the dynamic semantics. The static semantics comprises the definition of a concrete grammar, a set of correctness constraints, a set of transformation rules and an abstract syntax as basis for the dynamic semantics. The result of the static semantics is a representation of the specification in abstract syntax. The dynamic semantics starts with the abstract syntax. From here a behaviour model is derived based on the theory of Abstract State Machines (ASM). In order to keep the presentation intelligible a special abstract machine is defined using ASM. This abstract machine in fact represents an abstract SDL-machine. The formal semantics describes the properties of SDL exactly. However, in order to check the correctness of the formalisation, it has to be compared with the informal language description and the intentions of the language designers. This is most easily done using a correct implementation of the semantics. The implementation of the semantics is based on a representation of the input as an abstract syntax tree. For implementing the semantics with minimal effort existing tools are used. The compiler is produced using the standard tools lex and yacc. After parsing the remaining processing is defined over abstract syntax trees, which is covered by a tool called kimwitu. The formal semantics of RSDL is implemented using these tools. The same approach is applicable for SDL.

In Multi-Agenten-Systemen (MAS) kooperieren und konkurrieren Agenten um ihre jeweiligen Ziele zu erreichen. Für optimierte Agenten-Interaktionen sind Kenntnisse über die aktuellen und zukünftigen Handlungen anderer Agenten (Interaktionsparter, IP) hilfreich. Bei der Ermittlung und Nutzung solcher Kenntnisse kommt dem automatischen Erkennen und Verstehen sowie der Vorhersage von Verhalten der IP auf Basis von Beobachtungen besondere Bedeutung zu. Die Dissertation beschäftigt sich mit der automatischen Bestimmung und Vorhersage von Verhalten der IP durch einen Modellierenden Agenten (MA). Der MA generiert fallbasierte, adaptive Verhaltens-Modelle seiner IP und verwendet diese zur Vorhersage ihrer Verhalten. Als Anwendungsszenario wird mit dem virtuellen Fußballspiel des RoboCup ein komplexes und populäres MAS betrachtet. Der Hauptbeitrag dieser Arbeit besteht in der Ausarbeitung, Realisierung und Evaluierung eines Ansatzes zur automatischen Verhaltens-Modellierung für ein komplexes Multi-Agenten-System. / In multi-agent-systems agents cooperate and compete to reach their personal goals. For optimized agent interactions it is helpful for an agent to have knowledge about the current and future behavior of other agents. Ideally the recognition and prediction of behavior should be done automatically. This work addresses a way of automatically classifying and an attempt at predicting the behavior of a team of agents, based on external observation only. A set of conditions is used to distinguish behaviors and to partition the resulting behavior space. From observed behavior, team specific behavior models are then generated using Case Based Reasoning. These models, which are derived from a number of virtual soccer games (RoboCup), are used to predict the behavior of a team during a new game. The main contribution of this work is the design, realization and evaluation of an automatic behavior modeling approach for complex multi-agent systems.