Automatische Dienstvermittlung in dienstorientierten Architekturen in Aktion (ADDOaction)

In diesem Bericht werden die Ergebnisse und Fortschritte des Forschungsprojekts ADDOaction vorgestellt. Durch die Entwicklung in den letzten Jahrzehnten wurde das Internet zu einer wichtigen Infrastruktur für Geschäftsprozesse. Beliebige Anwendungen können als Dienste angeboten und übers Internet den Kunden online zur Verfügung gestellt werden. Eine flexible Dienstarchitektur ist dabei durch einen gewissen Grad an Dynamik gekennzeichnet, wo Dienste angepasst, ausgetauscht oder entfernt werden können und eventuell gleichzeitig von verschiedenen Anbietern bereitgestellt werden können. Dienste müssen dabei sowohl die funktionalen als auch die nicht-funktionalen Quality of Service (QoS) Anforderungen der Klienten erfüllen, um Kundenzufriedenheit garantieren zu können. Die Vielzahl der angebotenen Dienste und die unterschiedlichen Anforderungen der Klienten machen eine manuelle Entdeckung und ein manuelles Management der Dienste praktisch unmöglich. ADDOaction adressiert genau diese Probleme einer dienstorientierten Architektur und liefert innovative Lösungen von der automatischen Entdeckung von Diensten bis hin zur Überwachung und zum Management von Diensten zur Laufzeit.

20. Theorietag der GI-Fachgruppe "Automaten und Formale Sprachen''

Die Fachgruppe AFS (früher Fachgruppe 0.1.5) der Gesellschaft für Informatik veranstaltet seit 1991 einmal im Jahr ein Treffen der Fachgruppe im Rahmen eines Theorietags, der traditionell eineinhalb Tage dauert. Seit dem Jahr 1996 wird dem eigentlichen Theorietag noch ein eintägiger Workshop zu speziellen Themen der theoretischen Informatik vorangestellt. In diesem Jahr wurde der Theorietag vom Fachgebiet "Theoretische Informatik" des Fachbereichs Elektrotechnik/Informatik der Universität Kassel organisiert. Er fand vom 29.9. bis 1.10.2010 in Baunatal bei Kassel statt. Dabei stand der begleitende Workshop unter dem allgemeinen Thema "Ausgewählte Themen der Theoretischen Informatik". Als Vortragende für diesen Workshop konnten Carsten Damm (Göttingen), Markus Holzer (Giessen), Peter Leupold (Kassel), Martin Plátek (Prag) und Heribert Vollmer (Hannover) gewonnen werden. Das Programm des eigentlichen Theorietags bestand aus 20 Vorträgen sowie der Sitzung der Fachgruppe AFS. In diesem Band finden sich die Zusammenfassungen aller Vorträge sowohl des Workshops als auch des Theorietags. Desweiteren enthält er das Programm und die Liste aller Teilnehmer.

Generierung von XSL-Visualisierungen für TEI-Dokumente in Drupal

Die vorliegende Diplomarbeit, befasst sich mit der Darstellung von TEI-Dokumenten im Content-Management-System „Drupal“. Dazu wird ein Modul entwickelt, welches das einfache Publizieren von Dokumenten in diesem, auf der Extensible Markup Language (XML) basierenden Format, in Drupal ermöglicht. Das Modul bietet eine Oberfläche zum Hochladen dieser Dokumente an und stellt zusätzlich Optionen bereit, die es ermöglichen die Darstellung der angezeigten Dokumente zu beeinflussen. Dabei ist es durch ein spezielles Menü möglich, Farben, Schriftgröße und -art festzulegen. Die Konvertierung der Dokumente geschieht per XSL Transformation und basiert auf dem Ergebnis eines vorangegangenen Projekts. Die Darstellung wird angereichert durch dynamische Elemente, wie Anmerkungen des Autors oder die Möglichkeit zur Umschaltung zwischen verschiedenen Textversionen wie z.B. einer originalen und einer korrigierten Fassung. Diese Funktion ist durch eine Werkzeugleiste zugänglich, die im unteren Bereich eingeblendet wird und es auch ermöglicht Seitenzahlen, die im Dokument als solche erkannt wurden, zu suchen oder direkt aufzurufen.

Indexierung und erweiterte Suche für visualisierte TEI-Dokumente in Drupal

Die Diplomarbeit beschäftigt sich mit der erweiterten Suche innerhalb von Dokumenten, die im TEI-Lite kodierten Format im Content-Management-System Drupal vorliegen. Aufgrund des modularen Aufbaus von Drupal wird die erweiterte Suche in Form eines Moduls verwirklicht. In einem ersten Schritt werden die Merkmale der im TEI-Lite Format vorliegenden Dokumente beschrieben. Dies umfasst Angaben sowohl zur Definition des TEI-Standards als auch zu grundlegenden Dokumenteneingenschaften. Weiterhin wird auf das CMS Drupal eingegangen und die Konzepte bereits existierender Suchmodule betrachtet. Die Präsentation des entwickelten Konzeptes zur Implementierung eines Suchmoduls, das auf die Bedürfnisse von TEI-Lite standardisierten Dokumenten ausgerichtet ist, ergibt sich aus den vorangegangenen Arbeitsschritten. Daraus resultieren Ansätze zur Indexierung, Durchsuchbarkeit sowie der visuellen Präsentation der Suchergebnisse. Die Schilderung der Verwendung und der Funktionen, die das Modul nach abgeschlossenen Programmierarbeiten kennzeichnen, geht der Darstellung des Implementierungsvorgangs voran, der gleichsam den Kern der Diplomarbeit bildet. Unter Zuhilfenahme von Quelltext-Auszügen werden Details zu einzelnen Entwicklungsstadien präsentiert. Abschließend wird ein Ausblick auf weitere Optimierungsmöglichkeiten des erarbeiteten Suchmoduls gegeben.

Darstellungen von TEI-Dokumenten für E-Reader im EPUB-Standard

Um der wachsenden Popularität der E-Books Rechnung zu tragen, befasst sich diese Arbeit mit der Entwicklung eines Drupal-Moduls, welches TEI-Dokumente als EPUB-Version für E-Reader zum Download anbietet. Eine Plain Text- als auch die TEI/XML-Version werden zusätzlich zum Herunterladen bereitgestellt. Ziel ist es, das Modul so zu konzipieren, dass die Wahl verschiedener Textvarianten (Originalfassung oder korrigierte Version) sowie eine Bestimmung des Textumfangs (Haupttext inklusive Anmerkungen des Autors oder Haupttext inklusive Anmerkungen des Autors und des Herausgebers) möglich sind. Eine Auswahlliste erlaubt es dem Benutzer darüber hinaus, ausschließlich die Kapitel seiner Wahl herunterzuladen. Das Modul wird als Block implementiert, um seine variable Positionierung auf der Webseite gewährleisten zu können. Zudem wird eine Konfigurationsseite im administrativen Bereich von Drupal implementiert, die eine Gestaltung des Blocks sowie zahlreiche Einstellungsoptionen zur Verfügung stellt. Hierzu gehört z.B. die Auswahl der Metadaten, die auf den ersten beiden Seiten des E-Books angezeigt werden.

Fehlersuche im Modell - Modellbasiertes Testen und Debuggen

Kern der vorliegenden Arbeit ist die Erforschung von Methoden, Techniken und Werkzeugen zur Fehlersuche in modellbasierten Softwareentwicklungsprozessen. Hierzu wird zuerst ein von mir mitentwickelter, neuartiger und modellbasierter Softwareentwicklungsprozess, der sogenannte Fujaba Process, vorgestellt. Dieser Prozess wird von Usecase Szenarien getrieben, die durch spezielle Kollaborationsdiagramme formalisiert werden. Auch die weiteren Artefakte des Prozess bishin zur fertigen Applikation werden durch UML Diagrammarten modelliert. Es ist keine Programmierung im Quelltext nötig. Werkzeugunterstützung für den vorgestellte Prozess wird von dem Fujaba CASE Tool bereitgestellt. Große Teile der Werkzeugunterstützung für den Fujaba Process, darunter die Toolunterstützung für das Testen und Debuggen, wurden im Rahmen dieser Arbeit entwickelt. Im ersten Teil der Arbeit wird der Fujaba Process im Detail erklärt und unsere Erfahrungen mit dem Einsatz des Prozesses in Industrieprojekten sowie in der Lehre dargestellt. Der zweite Teil beschreibt die im Rahmen dieser Arbeit entwickelte Testgenerierung, die zu einem wichtigen Teil des Fujaba Process geworden ist. Hierbei werden aus den formalisierten Usecase Szenarien ausführbare Testfälle generiert. Es wird das zugrunde liegende Konzept, die konkrete technische Umsetzung und die Erfahrungen aus der Praxis mit der entwickelten Testgenerierung dargestellt. Der letzte Teil beschäftigt sich mit dem Debuggen im Fujaba Process. Es werden verschiedene im Rahmen dieser Arbeit entwickelte Konzepte und Techniken vorgestellt, die die Fehlersuche während der Applikationsentwicklung vereinfachen. Hierbei wurde darauf geachtet, dass das Debuggen, wie alle anderen Schritte im Fujaba Process, ausschließlich auf Modellebene passiert. Unter anderem werden Techniken zur schrittweisen Ausführung von Modellen, ein Objekt Browser und ein Debugger, der die rückwärtige Ausführung von Programmen erlaubt (back-in-time debugging), vorgestellt. Alle beschriebenen Konzepte wurden in dieser Arbeit als Plugins für die Eclipse Version von Fujaba, Fujaba4Eclipse, implementiert und erprobt. Bei der Implementierung der Plugins wurde auf eine enge Integration mit Fujaba zum einen und mit Eclipse auf der anderen Seite geachtet. Zusammenfassend wird also ein Entwicklungsprozess vorgestellt, die Möglichkeit in diesem mit automatischen Tests Fehler zu identifizieren und diese Fehler dann mittels spezieller Debuggingtechniken im Programm zu lokalisieren und schließlich zu beheben. Dabei läuft der komplette Prozess auf Modellebene ab. Für die Test- und Debuggingtechniken wurden in dieser Arbeit Plugins für Fujaba4Eclipse entwickelt, die den Entwickler bestmöglich bei der zugehörigen Tätigkeit unterstützen.

Unterstützung suboptimaler Regelkreise durch eine zentrale Korrektursteuerung

Evolutionäre Algorithmen werden gerne für Optimierungsaufgaben mit sehr vielen Freiheitsgraden eingesetzt. Eine spezielle Konvergenzeigenschaft, daß nämlich der Rechenaufwand nur mit der Wurzel der Anzahl der Unbekannten steigt, prädestiniert sie dafür. Die evolutionären Algorithmen haben aber auch noch eine weitere interessante Eigenschaft: Von der Zielfunktion wird nur verlangt, daß sie monoton ist - nichts weiter. Speziell wird, im Gegensatz zu gradientenbasierten Verfahren, keinerlei Ableitung von der Zielfunktion benötigt. Dadurch können evolutionäre Algorithmen auch in solchen Fällen eingesetzt werden, in denen Ableitungen der Zielfunktion nicht oder nur schwierig zu beschaffen sind. Die evolutionären Algorithmen kommen deshalb mit so geringen Anforderungen an die Zielfunktion aus, weil nur absolute Bewertungen einzelner Punkte (hier Vektoren) im Lösungsraum durch die Zielfunktion vorgenommen werden. Dafür werden eine gewisse Anzahl Punkte gleichzeitig betrachtet. Im direkten Vergleich untereinander relativ günstig liegende Punkte werden für die weitere Rechnung übernommen, die anderen verworfen. Aus den Komponenten der übernommenen Punkte werden nun zufällig neue Punkte zusammengesetzt und ein wenig verschoben. Dann schließt sich der Kreis, indem diese neuen Punkte ebenfalls bewertet werden. Im Verlauf einer solchen Iteration konvergiert die Punktmenge in der Regel gegen ein Optimum. Oft kommt es gerade zu Beginn der Iteration zu schnellen Fortschritten. In dieser Arbeit wird ein Verfahren vorgestellt, bei dem mit Hilfe von evolutionären Algorithmen verbessernde Eingriffe in laufenden Echtzeitsystemen vorgenommen werden. Was gut oder schlecht ist, wird zu diesem Zweck über die Zielfunktion für die Optimierung definiert. Da von der Zielfunktion letztlich das Verhalten des Gesamtsystems abhängt, sollte sie sorgfältig ausgewählt werden. Die Eingriffe in das System sind zeitlich begrenzte Steuertrajektorien. Sie werden zusätzlich zur permanent wirkenden Regelung auf das System aufgebracht. Um die Anzahl der zu optimierenden Variablen in Grenzen zu halten, werden die Steuertrajektorien durch wenige Parameter repräsentiert. Da die Steuertrajektorien im voraus berechnet werden müssen, wird das Systemverhalten mittels eines Modells für eine gewisse, in der Zukunft liegende, Zeitspanne vorhergesagt. Wird die geforderte Qualität während dieser Zeitspanne unterschritten, kann so schon im Vorfeld ein Optimierungslauf des evolutionären Algorithmus durchgeführt werden. Allerdings ist die zur Verfügung stehende Rechenzeit von vornherein begrenzt. Daher ist es wesentlich, daß die mit evolutionären Algorithmen häufig assoziierte lange Rechenzeit nicht benötigt wird. Tatsächlich läßt sich unter Umständen mit wenig Rechenzeit auskommen. Erstens wird nur mit wenigen Variablen gerechnet, zweitens kommt es bei dem beschriebenen Verfahren - halbwegs gutmütige Systeme vorausgesetzt - gar nicht auf die letzte Nachkommastelle, sondern (ähnlich wie bei Sliding-Mode-Regelungen) mehr auf eine Tendenz an. Da evolutionäre Algorithmen aber gerade zu Beginn einer Iteration die größten Fortschritte in Richtung des Optimums machen, kann schon nach vergleichsweise wenigen Schritten eine deutliche Verbesserung der Gesamtsituation erreicht werden. Gerade um eine schnelle Konvergenz zu erreichen, sind die spezielle Ausprägung und die Parameter des evolutionären Algorithmus mit Bedacht zu wählen. Dafür werden im Rahmen der Arbeit einige Experimente durchgeführt. Anhand der Ergebnisse der Experimente können konkrete Empfehlungen für eine günstige Konfiguration des evolutionären Algorithmus gegeben werden. Um es vorwegzunehmen: Zuviel Aufwand beim evolutionären Algorithmus zu treiben, lohnt sich nicht. Schon mit einfachen Konfigurationen können gute Ergebnisse erzielt werden. Die einzige Maßnahme, die sich bei den Experimenten tatsächlich als vorteilhaft herausstellte, war die Aufteilung der Gesamtpopulation (betrachtete Punktmenge im Lösungsraum) in mehrere Subpopulationen. Schließlich wird noch ein Computerprogramm beschrieben, das die Arbeitsweise des vorgestellten Verfahrens am Bildschirm erlebbar macht. Die einzelnen Komponenten werden vom Programm während der Ausführung mit einigen wesentlichen Rechengrößen visualisiert. Der Betrachter erhält so einen besseren Eindruck vom Zusammenwirken der einzelnen Verfahrens-Teile.

Akzeptanz und Motivation beim selbstregulierten Lernen unter Einsatz von neuen Medien in der berufsbegleitenden Weiterbildung

Das Ziel der Dissertation war die Untersuchung des Computereinsatzes zur Lern- und Betreuungsunterstützung beim selbstgesteuerten Lernen in der Weiterbildung. In einem bisher konventionell durchgeführten Selbstlernkurs eines berufsbegleitenden Studiengangs, der an das Datenmanagement der Bürodatenverarbeitung heranführt, wurden die Kursunterlagen digitalisiert, die Betreuung auf eine online-basierte Lernbegleitung umgestellt und ein auf die neuen Lernmedien abgestimmtes Lernkonzept entwickelt. Dieses neue Lernkonzept wurde hinsichtlich der Motivation und der Akzeptanz von digitalen Lernmedien evaluiert. Die Evaluation bestand aus zwei Teilen: 1. eine formative, den Entwicklungsprozess begleitende Evaluation zur Optimierung der entwickelten Lernsoftware und des eingeführten Lernkonzeptes, 2. eine sowohl qualitative wie quantitative summative Evaluation der Entwicklungen. Ein zentraler Aspekt der Untersuchung war die freie Wahl der Lernmedien (multimediale Lernsoftware oder konventionelles Begleitbuch) und der Kommunikationsmedien (online-basierte Lernplattform oder die bisher genutzten Kommunikationskanäle: E-Mail, Telefon und Präsenztreffen). Diese Zweigleisigkeit erlaubte eine differenzierte Gegenüberstellung von konventionellen und innovativen Lernarrangements. Die Verbindung von qualitativen und quantitativen Vorgehensweisen, auf Grund derer die subjektiven Einstellungen der Probanden in das Zentrum der Betrachtung rückten, ließen einen Blickwinkel auf den Nutzen und die Wirkung der Neuen Medien in Lernprozessen zu, der es erlaubte einige in der Literatur als gängig angesehene Interpretationen in Frage zu stellen und neu zu diskutieren. So konnten durch eine Kategorisierung des Teilnehmerverhaltens nach online-typisch und nicht online-typisch die Ursache-Wirkungs-Beziehungen der in vielen Untersuchungen angeführten Störungen in Online-Seminaren verdeutlicht werden. In den untersuchten Kursen zeigte sich beispielsweise keine Abhängigkeit der Drop-out-Quote von den Lern- und Betreuungsformen und dass diese Quote mit dem neuen Lernkonzept nur geringfügig beeinflusst werden konnte. Die freie Wahl der Lernmedien führte zu einer gezielten Nutzung der multimedialen Lernsoftware, wodurch die Akzeptanz dieses Lernmedium stieg. Dagegen war die Akzeptanz der Lernenden gegenüber der Lernbegleitung mittels einer Online-Lernplattform von hoch bis sehr niedrig breit gestreut. Unabhängig davon reichte in allen Kursdurchgängen die Online-Betreuung nicht aus, so dass Präsenztreffen erbeten wurde. Hinsichtlich der Motivation war die Wirkung der digitalen Medien niedriger als erwartet. Insgesamt bieten die Ergebnisse Empfehlungen für die Planung und Durchführung von computerunterstützten, online-begleiteten Kursen.

Large-Size AlGaN/GaN HEMT Large-Signal Electrothermal Characterization and Modeling for Wireless Digital Communications

The rapid growth in high data rate communication systems has introduced new high spectral efficient modulation techniques and standards such as LTE-A (long term evolution-advanced) for 4G (4th generation) systems. These techniques have provided a broader bandwidth but introduced high peak-to-average power ratio (PAR) problem at the high power amplifier (HPA) level of the communication system base transceiver station (BTS). To avoid spectral spreading due to high PAR, stringent requirement on linearity is needed which brings the HPA to operate at large back-off power at the expense of power efficiency. Consequently, high power devices are fundamental in HPAs for high linearity and efficiency. Recent development in wide bandgap power devices, in particular AlGaN/GaN HEMT, has offered higher power level with superior linearity-efficiency trade-off in microwaves communication. For cost-effective HPA design to production cycle, rigorous computer aided design (CAD) AlGaN/GaN HEMT models are essential to reflect real response with increasing power level and channel temperature. Therefore, large-size AlGaN/GaN HEMT large-signal electrothermal modeling procedure is proposed. The HEMT structure analysis, characterization, data processing, model extraction and model implementation phases have been covered in this thesis including trapping and self-heating dispersion accounting for nonlinear drain current collapse. The small-signal model is extracted using the 22-element modeling procedure developed in our department. The intrinsic large-signal model is deeply investigated in conjunction with linearity prediction. The accuracy of the nonlinear drain current has been enhanced through several issues such as trapping and self-heating characterization. Also, the HEMT structure thermal profile has been investigated and corresponding thermal resistance has been extracted through thermal simulation and chuck-controlled temperature pulsed I(V) and static DC measurements. Higher-order equivalent thermal model is extracted and implemented in the HEMT large-signal model to accurately estimate instantaneous channel temperature. Moreover, trapping and self-heating transients has been characterized through transient measurements. The obtained time constants are represented by equivalent sub-circuits and integrated in the nonlinear drain current implementation to account for complex communication signals dynamic prediction. The obtained verification of this table-based large-size large-signal electrothermal model implementation has illustrated high accuracy in terms of output power, gain, efficiency and nonlinearity prediction with respect to standard large-signal test signals.

Kontextbasiertes System zur Vermeidung von Kollisionen zwischen Autos und Fußgängern

Laut dem Statistischen Bundesamts ist die Zahl der im Straßenverkehr getöteten Personen zwar rückläufig, jedoch wurden in 2010 in Deutschland noch immer 3648 Personen bei Unfällen im Straßenverkehr getötet, 476 davon waren Fußgänger. In den letzten Dekaden lag der Schwerpunkt der Forschungsarbeiten zur Reduzierung der Verkehrstoten besonders im Bereich des Insassenschutzes. Erst in den letzten Jahren rückte die Thematik des Fußgängerschutzes mehr in den Fokus des öffentlichen Interesses und der Automobilhersteller. Forschungsarbeiten beschäftigen sich mit unterschiedlichen Ansätzen die Folgen einer Kollision zwischen einem Auto und einem Fußgänger zu reduzieren. Hierzu zählen z.B. weiche Aufprallzonen im Frontbereich eines Autos, aufstellende Motorhaube oder auch Fußgängerairbags im Bereich der Frontscheibe. Da passive Ansätze aber nur die Folgen eines Aufpralls am Fahrzeug, nicht aber die Folgen eines Sekundäraufpralls auf dem Boden verringern können, werden parallel Ansätze zur aktiven Kollisionsvermeidung untersucht. Die bisher verfolgten, ebenso wertvollen Ansätze, zeigen jedoch jeweils Schwachpunkte in Ihrer Lösung. So ist der Einsatz der bisherigen bordautonomen Ansätze auf Grund der Anforderungen der verschiedenen Systeme, wie der Notwendigkeit einer direkten, ungestörten Sichtverbindung zwischen Auto und Fußgänger, leider nur eingeschränkt möglich. Kooperative Systeme, die ein zusätzliches, vom Fußgänger mitzuführendes Sende-Empfänger Gerät zur Ermittlung der Fußgängerposition benötigen sind hingegen mit zusätzlichem Aufwand für den Fußgänger verbunden. Auch fehlen den bisher verfolgten Ansätzen Informationen über den Fußgänger, wodurch es schwierig ist, wenn nicht gar manchmal unmöglich, eine Situation korrekt bewerten zu können. Auch sehen diese Systeme keine Warnung des Fußgängers vor. In dieser Arbeit wird ein Verfahren zum Fußgängerschutz betrachtet, welches per Funk ausgetauschte Informationen zur Risikobewertung eines Szenarios nutzt. Hierbei werden neben den vom Auto bekannten Informationen und Parameter, die vom Smartphone des Fußgängers zur Verfügung gestellten Kontextinformationen verwendet. Es werden zum einen die Parameter, Bedingungen und Anforderungen analysiert und die Architektur des Systems betrachtet. Ferner wird das Ergbnis einer Untersuchung zur generellen Umsetzbarkeit mit bereits heute in Smartphone verfügbaren Funktechnolgien vorgestellt. Final werden die bereits vielversprechenden Ergebnisse eines ersten Experiments zur Nutzbarkeit von Sensorinformationen des Smartphones im Bereich der Kollisionsvermeidung vorgestellt und diskutiert.

On the Benefits of Abstraction in Concurrent Haskell

Heutzutage haben selbst durchschnittliche Computersysteme mehrere unabhängige Recheneinheiten (Kerne). Wird ein rechenintensives Problem in mehrere Teilberechnungen unterteilt, können diese parallel und damit schneller verarbeitet werden. Obwohl die Entwicklung paralleler Programme mittels Abstraktionen vereinfacht werden kann, ist es selbst für Experten anspruchsvoll, effiziente und korrekte Programme zu schreiben. Während traditionelle Programmiersprachen auf einem eher geringen Abstraktionsniveau arbeiten, bieten funktionale Programmiersprachen wie z.B. Haskell, Möglichkeiten zur fortgeschrittenen Abstrahierung. Das Ziel der vorliegenden Dissertation war es, zu untersuchen, wie gut verschiedene Arten der Abstraktion das Programmieren mit Concurrent Haskell unterstützen. Concurrent Haskell ist eine Bibliothek für Haskell, die parallele Programmierung auf Systemen mit gemeinsamem Speicher ermöglicht. Im Mittelpunkt der Dissertation standen zwei Forschungsfragen. Erstens wurden verschiedene Synchronisierungsansätze verglichen, die sich in ihrem Abstraktionsgrad unterscheiden. Zweitens wurde untersucht, wie Abstraktionen verwendet werden können, um die Komplexität der Parallelisierung vor dem Entwickler zu verbergen. Bei dem Vergleich der Synchronisierungsansätze wurden Locks, Compare-and-Swap Operationen und Software Transactional Memory berücksichtigt. Die Ansätze wurden zunächst bezüglich ihrer Eignung für die Synchronisation einer Prioritätenwarteschlange auf Basis von Skiplists untersucht. Anschließend wurden verschiedene Varianten des Taskpool Entwurfsmusters implementiert (globale Taskpools sowie private Taskpools mit und ohne Taskdiebstahl). Zusätzlich wurde für das Entwurfsmuster eine Abstraktionsschicht entwickelt, welche eine einfache Formulierung von Taskpool-basierten Algorithmen erlaubt. Für die Untersuchung der Frage, ob Haskells Abstraktionsmethoden die Komplexität paralleler Programmierung verbergen können, wurden zunächst stencil-basierte Algorithmen betrachtet. Es wurde eine Bibliothek entwickelt, die eine deklarative Beschreibung von stencil-basierten Algorithmen sowie ihre parallele Ausführung erlaubt. Mit Hilfe dieses deklarativen Interfaces wurde die parallele Implementation vollständig vor dem Anwender verborgen. Anschließend wurde eine eingebettete domänenspezifische Sprache (EDSL) für Knoten-basierte Graphalgorithmen sowie eine entsprechende Ausführungsplattform entwickelt. Die Plattform erlaubt die automatische parallele Verarbeitung dieser Algorithmen. Verschiedene Beispiele zeigten, dass die EDSL eine knappe und dennoch verständliche Formulierung von Graphalgorithmen ermöglicht.

Capturing Emergent Semantics from Social Annotation Systems

The ongoing growth of the World Wide Web, catalyzed by the increasing possibility of ubiquitous access via a variety of devices, continues to strengthen its role as our prevalent information and commmunication medium. However, although tools like search engines facilitate retrieval, the task of finally making sense of Web content is still often left to human interpretation. The vision of supporting both humans and machines in such knowledge-based activities led to the development of different systems which allow to structure Web resources by metadata annotations. Interestingly, two major approaches which gained a considerable amount of attention are addressing the problem from nearly opposite directions: On the one hand, the idea of the Semantic Web suggests to formalize the knowledge within a particular domain by means of the "top-down" approach of defining ontologies. On the other hand, Social Annotation Systems as part of the so-called Web 2.0 movement implement a "bottom-up" style of categorization using arbitrary keywords. Experience as well as research in the characteristics of both systems has shown that their strengths and weaknesses seem to be inverse: While Social Annotation suffers from problems like, e. g., ambiguity or lack or precision, ontologies were especially designed to eliminate those. On the contrary, the latter suffer from a knowledge acquisition bottleneck, which is successfully overcome by the large user populations of Social Annotation Systems. Instead of being regarded as competing paradigms, the obvious potential synergies from a combination of both motivated approaches to "bridge the gap" between them. These were fostered by the evidence of emergent semantics, i. e., the self-organized evolution of implicit conceptual structures, within Social Annotation data. While several techniques to exploit the emergent patterns were proposed, a systematic analysis - especially regarding paradigms from the field of ontology learning - is still largely missing. This also includes a deeper understanding of the circumstances which affect the evolution processes. This work aims to address this gap by providing an in-depth study of methods and influencing factors to capture emergent semantics from Social Annotation Systems. We focus hereby on the acquisition of lexical semantics from the underlying networks of keywords, users and resources. Structured along different ontology learning tasks, we use a methodology of semantic grounding to characterize and evaluate the semantic relations captured by different methods. In all cases, our studies are based on datasets from several Social Annotation Systems. Specifically, we first analyze semantic relatedness among keywords, and identify measures which detect different notions of relatedness. These constitute the input of concept learning algorithms, which focus then on the discovery of synonymous and ambiguous keywords. Hereby, we assess the usefulness of various clustering techniques. As a prerequisite to induce hierarchical relationships, our next step is to study measures which quantify the level of generality of a particular keyword. We find that comparatively simple measures can approximate the generality information encoded in reference taxonomies. These insights are used to inform the final task, namely the creation of concept hierarchies. For this purpose, generality-based algorithms exhibit advantages compared to clustering approaches. In order to complement the identification of suitable methods to capture semantic structures, we analyze as a next step several factors which influence their emergence. Empirical evidence is provided that the amount of available data plays a crucial role for determining keyword meanings. From a different perspective, we examine pragmatic aspects by considering different annotation patterns among users. Based on a broad distinction between "categorizers" and "describers", we find that the latter produce more accurate results. This suggests a causal link between pragmatic and semantic aspects of keyword annotation. As a special kind of usage pattern, we then have a look at system abuse and spam. While observing a mixed picture, we suggest that an individual decision should be taken instead of disregarding spammers as a matter of principle. Finally, we discuss a set of applications which operationalize the results of our studies for enhancing both Social Annotation and semantic systems. These comprise on the one hand tools which foster the emergence of semantics, and on the one hand applications which exploit the socially induced relations to improve, e. g., searching, browsing, or user profiling facilities. In summary, the contributions of this work highlight viable methods and crucial aspects for designing enhanced knowledge-based services of a Social Semantic Web.

Systems of Parallel Communicating Restarting Automata

In der vorliegenden Dissertation werden Systeme von parallel arbeitenden und miteinander kommunizierenden Restart-Automaten (engl.: systems of parallel communicating restarting automata; abgekürzt PCRA-Systeme) vorgestellt und untersucht. Dabei werden zwei bekannte Konzepte aus den Bereichen Formale Sprachen und Automatentheorie miteinander vescrknüpft: das Modell der Restart-Automaten und die sogenannten PC-Systeme (systems of parallel communicating components). Ein PCRA-System besteht aus endlich vielen Restart-Automaten, welche einerseits parallel und unabhängig voneinander lokale Berechnungen durchführen und andererseits miteinander kommunizieren dürfen. Die Kommunikation erfolgt dabei durch ein festgelegtes Kommunikationsprotokoll, das mithilfe von speziellen Kommunikationszuständen realisiert wird. Ein wesentliches Merkmal hinsichtlich der Kommunikationsstruktur in Systemen von miteinander kooperierenden Komponenten ist, ob die Kommunikation zentralisiert oder nichtzentralisiert erfolgt. Während in einer nichtzentralisierten Kommunikationsstruktur jede Komponente mit jeder anderen Komponente kommunizieren darf, findet jegliche Kommunikation innerhalb einer zentralisierten Kommunikationsstruktur ausschließlich mit einer ausgewählten Master-Komponente statt. Eines der wichtigsten Resultate dieser Arbeit zeigt, dass zentralisierte Systeme und nichtzentralisierte Systeme die gleiche Berechnungsstärke besitzen (das ist im Allgemeinen bei PC-Systemen nicht so). Darüber hinaus bewirkt auch die Verwendung von Multicast- oder Broadcast-Kommunikationsansätzen neben Punkt-zu-Punkt-Kommunikationen keine Erhöhung der Berechnungsstärke. Desweiteren wird die Ausdrucksstärke von PCRA-Systemen untersucht und mit der von PC-Systemen von endlichen Automaten und mit der von Mehrkopfautomaten verglichen. PC-Systeme von endlichen Automaten besitzen bekanntermaßen die gleiche Ausdrucksstärke wie Einwegmehrkopfautomaten und bilden eine untere Schranke für die Ausdrucksstärke von PCRA-Systemen mit Einwegkomponenten. Tatsächlich sind PCRA-Systeme auch dann stärker als PC-Systeme von endlichen Automaten, wenn die Komponenten für sich genommen die gleiche Ausdrucksstärke besitzen, also die regulären Sprachen charakterisieren. Für PCRA-Systeme mit Zweiwegekomponenten werden als untere Schranke die Sprachklassen der Zweiwegemehrkopfautomaten im deterministischen und im nichtdeterministischen Fall gezeigt, welche wiederum den bekannten Komplexitätsklassen L (deterministisch logarithmischer Platz) und NL (nichtdeterministisch logarithmischer Platz) entsprechen. Als obere Schranke wird die Klasse der kontextsensitiven Sprachen gezeigt. Außerdem werden Erweiterungen von Restart-Automaten betrachtet (nonforgetting-Eigenschaft, shrinking-Eigenschaft), welche bei einzelnen Komponenten eine Erhöhung der Berechnungsstärke bewirken, in Systemen jedoch deren Stärke nicht erhöhen. Die von PCRA-Systemen charakterisierten Sprachklassen sind unter diversen Sprachoperationen abgeschlossen und einige Sprachklassen sind sogar abstrakte Sprachfamilien (sogenannte AFL's). Abschließend werden für PCRA-Systeme spezifische Probleme auf ihre Entscheidbarkeit hin untersucht. Es wird gezeigt, dass Leerheit, Universalität, Inklusion, Gleichheit und Endlichkeit bereits für Systeme mit zwei Restart-Automaten des schwächsten Typs nicht semientscheidbar sind. Für das Wortproblem wird gezeigt, dass es im deterministischen Fall in quadratischer Zeit und im nichtdeterministischen Fall in exponentieller Zeit entscheidbar ist.