Filtern
Erscheinungsjahr
Dokumenttyp
- Dissertation (26) (entfernen)
Volltext vorhanden
- ja (26) (entfernen)
Schlagworte
- Algorithmus (3)
- Middleware (3)
- Abfrageverarbeitung (2)
- Ad-hoc-Netz (2)
- Mobile Computing (2)
- OBDD (2)
- OBDDs (2)
- Peer-to-Peer-Netz (2)
- Selbstorganisation (2)
- mobile computing (2)
- (general) boustrophedon (returning) finite automata (1)
- (general) jumping finite automata (1)
- (regular : regular) array grammars (1)
- (regulär: regulär) Array-Grammati (1)
- Algorithmische Lerntheorie (1)
- Amortisierte Laufzeitanalyse (1)
- Amortized run time analysis (1)
- Analyse (1)
- Ankunftsprozess (1)
- Applikationsunterstützung (1)
- Automata Theory (1)
- Automatentheorie (1)
- BMAP (1)
- Bilddatenverarbeitung (1)
- Client-server-Konzept (1)
- Cluster (1)
- Consistency (1)
- DICOM-image (1)
- Datenspeicherung (1)
- Datenstruktur (1)
- Datenverdichtung (1)
- Directed Graphs (1)
- Disambiguierung von Personennamen (1)
- Distributed Systems (1)
- Dokumentverarbeitung (1)
- E-Learning (1)
- Elektronische Bibliothek (1)
- Erweiterung (1)
- Eulerian trails (1)
- Exact Algorithms (1)
- Exakte Algorithmen (1)
- Exponental time algorithms (1)
- Exponentialzeit Algorithmen (1)
- Fallbasiertes Schließen (1)
- Flussdiagramm (1)
- Formal Verification (1)
- Formal languages (1)
- Gerichteter Graph (1)
- Graph Minors (1)
- Graph Rewriting (1)
- Graph Visualization (1)
- Graphen mit Eulerschen Pfaden (1)
- Graphvisualisierung (1)
- Hyperlink-Management (1)
- Hyperlink-Proposals (1)
- Immersion <Virtuelle Realität> (1)
- Information Visualization (1)
- Informationssystem (1)
- Informationsvisualisierung (1)
- Integrated Circuits (1)
- Internet (1)
- Internetdienst (1)
- Kollaboration <Informatik> (1)
- Kom (1)
- Kombinatorische Optimierung (1)
- Komplexe Netzwerke (1)
- Komplexe Systeme (1)
- Komplexität (1)
- Komponente <Software> (1)
- Konsistenz (1)
- Logischer Entwurf (1)
- MMVE (1)
- Markov Jump Process (1)
- Markov-Kette (1)
- Markov-Prozess (1)
- Mathematische Lerntheorie (1)
- Measure & Conquer (1)
- Metadaten (1)
- Minor <Graphentheorie> (1)
- Mobile Networks (1)
- Mobile Telekommunikation (1)
- Modellierung (1)
- Multicast Communication (1)
- Multicastingverfahren (1)
- NP-hartes Problem (1)
- Netzwerk (1)
- Netzwerksimulation (1)
- Nichtlineare Dynamik (1)
- Näherungsverfahren (1)
- Operations Research (1)
- Ordered Binary Decision Diagrams (1)
- Overlay Network (1)
- Overlay-Netz (1)
- Parameterisierte Algorithmen (1)
- Parameterized Algorithms (1)
- Parametrisierte Approximation (1)
- Peer-to-Peer Network (1)
- Periodic Queues (1)
- Personenname (1)
- Pipeline (1)
- Prozessor (1)
- Pufferspeicher (1)
- Queues (1)
- RPC (1)
- Radiologie (1)
- Rechnernetz (1)
- Reduktionssystem (1)
- Regular Expressions (1)
- Regulärer Ausdruck (1)
- Request-Prediction (1)
- Robustheit (1)
- Server (1)
- Software Visualization (1)
- Softwarevisualisierung (1)
- Speicherdirektzugriff (1)
- Standard ML (1)
- Statistical Mechanics of complex networks (1)
- Statistische Mechanik komplexer Netze (1)
- Store-And-Forward Network (1)
- Store-And-Forward Netzwerk (1)
- Streaming <Kommunikationstechnik> (1)
- Synchronisierung (1)
- Synergie (1)
- Syntaktische Analyse (1)
- Telekommunikationsnetz (1)
- Theoretische Informatik (1)
- Transitionssystem (1)
- Verifikation (1)
- Verteiltes System (1)
- Virtual Environment (1)
- Virtuelle Realität (1)
- Virtuelle Umgebung (1)
- Visualisierung (1)
- Visualization (1)
- Warteschlangentheorie (1)
- Wartesystem (1)
- Web-Applications (1)
- Website-Management (1)
- Weitverkehrsnetz (1)
- Workflow-Programm (1)
- XML (1)
- XOR Parity (1)
- Zufallsgraph (1)
- ad-hoc network (1)
- algorithm analysis (1)
- application support (1)
- archiving (1)
- cache behavior (1)
- clustering (1)
- complex networks (1)
- complex systems (1)
- complexity (1)
- compression (1)
- computational geometry (1)
- controlled queueing system (1)
- convex hull (1)
- digital library (1)
- divide and conquer (1)
- endliche Boustrophedon-Automaten (1)
- formal verification (1)
- grammatical inference (1)
- historical metadata (1)
- home pages (1)
- incremental algorithm (1)
- information retrieval (1)
- jumping endliche Automaten (1)
- memory distance (1)
- middleware (1)
- mobile Telekommunikation (1)
- mobile ad-hoc network (1)
- multicore (1)
- multihop Netzwerk (1)
- multihop network (1)
- network simulation (1)
- numerical analysis (1)
- optimal control (1)
- parameterised approximation (1)
- partitioning (1)
- person name disambiguation (1)
- processing (1)
- radiology (1)
- reordering (1)
- search engine (1)
- threshold (1)
- time complexity (1)
- web-based services (1)
- zurückkehrende(RFA) (1)
Institut
- Informatik (26) (entfernen)
Insbesondere im wissenschaftlichen Bereich ist es zur Selbstverständlichkeit geworden, zur Befriedigung eines Informationsbedürfnisses zunächst das World Wide Web (Web) zu benutzen. Der komplexe Aufbau des Webs und die dort herrschende Unordnung machen das Auffinden bestimmter Dokumente zu einem diffizilen Vorgang. Suchmaschinen und Web-Verzeichnisse unterstützen den Benutzer hierbei; ihre effektive Nutzung ist jedoch nicht einfach. Es ist daher hilfreich, Suchdienste zu entwickeln, welche Kontextwissen mitbringen. In der vorliegenden Arbeit wird das Verfahren der thematisch spezialisierten Suche präsentiert und anhand der Menge der persönlicher Home Pages von Informatikern exemplifiziert. Der Bibliographie-Server DBLP.uni-trier.de liefert u.a. zu über 4.000 Wissenschaftlern manuell gesammelte persönliche Home Pages. Durch verschiedene Analysen werden in dieser Menge häufig vorkommende, also relevante Eigenschaften ermittelt. Dies ist ein kreativer Prozess, in den sowohl Suchwissen -- Wissen über Techniken des Suchens im Web -- als auch Fachwissen -- Wissen über die Beschaffenheit persönlicher Home Pages -- einfließen. Nach der Überprüfung dieser Eigenschaften auf ihre Signifikanz in der Gesamtheit der Web-Dokumente ist ein thematisch spezialisiertes Wissen erschaffen worden. Zur Durchführung der Suche würde man idealerweise alle Web-Dokumente mit Hilfe des erarbeiteten Wissens und des Anfrageterms -- des vollständigen Namens eines Informatikers -- untersuchen. Da das Web aus mehreren Milliarden Dokumenten besteht, ist dies praktisch nicht durchführbar: Es ist notwendig, eine geeignete Vorauswahl zu treffen. Suchmaschinen haben Daten zu vielen Web-Dokumenten erfasst. Deshalb wird mit ihrer Hilfe unter Verwendung des Anfrageterms eine Vorauswahl getroffen. Um nun die Dokumente der Vorauswahlmenge gemäß der Anfrage zu bewerten wird das thematisch spezialisierte Wissen adäquat in einer Bewertungsfunktion repräsentiert, welche jedem Dokument einen Wert zuweist und somit eine Rangfolge erstellt. Das Design der Bewertungsfunktion ist eine schöpferische Tätigkeit: Die sachgerechte Gewichtung der verschiedenen Eigenschaften bestimmt maßgeblich das Gelingen des Verfahrens. Der vornehmlich in Java implementierte, vollautomatisierte Web-Dienst HomePageSearch (hpsearch.uni-trier.de) führt regelmäßig für über 100.000 Namen diesen Suchvorgang durch. Der Benutzer kann auf das in einer DB2-Datenbank gespeicherte Ergebnis zurückgreifen. Durch die periodische Neuberechnung des thematisch spezialisierten Wissens wird der Dynamik des Webs Rechnung getragen. Der modulare und stark parametrisierte Aufbau des Systems erleichtert die Portierung des Verfahrens auf andere Mengen von Web-Dokumenten. Nicht zuletzt aufgrund der starken Verlinkung mit DBLP und ResearchIndex wird HomePageSearch von vielen Wissenschaftlern intensiv genutzt.
In den letzten Jahren führte die intensive Forschung im Bereich der Hochleistungskommunikationsnetze zu kontinuierlichen technologischen Verbesserungen. Gegenwärtig ist eine schnell wachsende Nachfrage nach mobilen Kommunikationssystemen wie Mobiltelefonen oder kabellosen Computernetzen zu verzeichnen. Parallel zu diesen Entwicklungen stiegen die Anforderungen an die Methoden zur Leistungsanalyse derartiger Systeme. Die Warteschlangentheorie stellt klassische Modelle zur Analyse von Kommunikationsnetzen bereit. Ein Bereich in der modernen Warteschlangentheorie sind die Matrixanalytischen Methoden. Hier konzentriert sich die Forschung auf den Batch Markovian Arrival Process (BMAP), welcher äquivalent zu Neuts Versatile Markovian Point Process ist, und Warteschlangensysteme mit diesem Ankunftsprozeß. Der BMAP ist eine Verallgemeinerung des Poisson Prozesses, des Markov Modulated Poisson Process (MMPP) und des Markovian Arrival Process (MAP). Das BMAP/G/1 Warteschlangensystem wurde analysiert von Ramaswami (damals noch mit der Bezeichnung N/G/1) und Lucantoni. Weitere Varianten wurden später untersucht. Die bisher betrachteten Ankunftsprozesse sind räumlich homogen und somit unabhängig vom aktuellen Zustand des Warteschlangensystems. In modernen Kommunikationsnetzen, wie z.B. ATM, kann jedoch ein dynamisches Routing erfolgen, so daß der Ankunftsstrom in einen Knoten vom aktuellen Zustand dieses Knotens abhängt. Dies war unser Ausgangspunkt für die Definition eines Level-abhängigen BMAPs und die Analyse des BMAP/G/1 Warteschlangensystems mit Level-abhängigen Ankünften. Letzteres stellt eine Verallgemeinerung des klassischen BMAP/G/1 Warteschlangensystems dar. Es umfaßt auch das BMAP/G/1 Warteschlangensystem mit beschränktem Warteraum. Im ersten Teil dieser Arbeit definieren wir einen Level-abhängigen BMAP und leiten wichtige Eigenschaften der Generatormatrix und der Übergangswahrscheinlichkeiten her. Wir zeigen, daß die Übergangsmatrix des Level-abhängigen BMAPs die Vorwärts- und Rückwärtsdifferentialgleichungen erfüllt und somit als Matrixexponentialfunktion der Generatormatrix darstellbar ist. Der zweite Teil befaßt sich mit der Analyse des BMAP/G/1 Warteschlangensystems mit Level-abhängigen Ankünften. Dieses Warteschlangensystem und die zugehörigen stochastischen Prozesse werden in Kapitel 2 eingeführt. Um die Grenzverteilung der Warteschlangenlänge zu bestimmen, verwenden wir die Methode der eingebetteten Markov Kette. In Kapitel 3 bestimmen wir die Einträge der Übergangsmatrix der eingebetteten Markov Kette und die mittlere Zahl Ankünfte während einer Bedienzeit. Stabilitätsbedingungen für das BMAP/G/1 Warteschlangensystem mit Level- abhängigen Ankünften werden durch Anwendung eines verallgemeinerten Foster Kriteriums hergeleitet. Im Level-unabhängigen Fall spielt die Fundamentalperiodenmatrix G die Hauptrolle bei der Bestimmung der Gleichgewichtsverteilung. In unserem Fall hängen die Fundamentalperioden vom Anfangslevel k ab. Daher erhalten wir verschiedene Fundamentalperiodenmatrizen G ( k ) für alle Level k >= 1 . Wir leiten zwei Algorithmen zur Berechnung dieser Matrizen her. Weiterhin zeigen wir, daß die Vektoren der mittleren Anzahlen Bedienabschlüsse während einer Fundamentalperiode die eindeutige Lösung eines unendlich - dimensionalen Systems linearer Gleichungen bilden. Mit diesen Ergebnissen kann die stationäre Verteilung der Warteschlangenlänge zu Bedienabschlußzeitpunkten bestimmt werden. Wir wenden ein Ergebnis aus der Theorie der Semi-Markov Prozesse an, um die Gleichgewichtswahrscheinlichkeiten für Level 0 zu erhalten. Um die Gleichgewichtswahrscheinlichkeiten der übrigen Level zu berechnen, verallgemeinern wir die Formel von Ramaswami. Die Grenzverteilung der Warteschlangenlänge zu beliebigen Zeitpunkten wird unter Verwendung des Hauptsatzes der Erneuerungstheorie hergeleitet. Im dritten Teil betrachten wir einige Spezialfälle. Zunächst nehmen wir an, daß der Phasenprozeß Level-unabhängig sei. In diesem Fall können wir einige unserer Ergebnisse erweitern. Insbesondere leiten wir eine stärkere Stabilitätsbedingung her. Wir beenden diesen Teil, indem wir zeigen, daß unsere Ergebnisse mit den für das klassische BMAP/G/1 Warteschlangensystem und das BMAP/G/1 Warteschlangensystem mit beschränktem Warteraum übereinstimmen. Zum Abschluß dieser Arbeit geben wir einige Hinweise für weitere Forschungen.
Synergieeffekte und Kollaboration bei e-Learning-Anwendungen in selbstorganisierenden Computernetzen
(2009)
In den letzten Jahren haben sich mehrere neue Netzklassen im Bereich der Verteilten Systeme etabliert. Diese können unter Ausnutzung von Selbstorganisationsprinzipien und verschiedener kollaborativer Aspekte viele der netzinhärenten Probleme wie Skalierbarkeit, Latenz- und Lastverteilungsbetrachtungen sowie Konsistenzwahrung entschärfen. Gleichzeitig kann die Nutzung entsprechender Prinzipien zu positiven Synergieeffekten führen, die von den verschiedenen auf diesen Netzen aufsetzten Applikationsdomänen genutzt werden können. Von besonderer Bedeutung sind diese Aspekte für die beiden neuartigen Netzklassen der Multi-Hop Adhoc-Netze (MANETs) und der globalen virtuellen Umgebungen (MMVEs). Beiden Netzklassen ist gemeinsam, dass sie aufgrund der erwähnten Problemstellungen nicht mit traditionellen verteilten Architekturen, wie zentralistischen und monolithischen Systemen, umgesetzt werden können. Hier muss ein Paradigmenwechsel hin zu dezentralen, selbstorganisierenden Systemstrukturen erfolgen, um den angesprochenen Herausforderungen zu begegnen. Die erste in dieser Arbeit untersuchte Netzklasse der MANETs zeichnet sich dadurch aus, dass sie Nutzern erlaubt, immer und überall auf Ihre Daten zugreifen zu können und mit der vor Ort vorhandenen Infrastruktur transparent zu kommunizieren. Dabei erfolgen die Daten-zugriffe vermehrt über immer kleiner werdende mobile Endgeräte, die sowohl aufgrund ihrer inhärenten Mobilität als auch ihrer eingeschränkten Ressourcen daran angepasste Netzstrukturen erfordern. Die neuartige Netzklasse der MMVEs dagegen soll Dateninhalte in einem dreidimensionalen Rahmen und damit nativ und intuitiver als die vorherrschende zweidimensionale Darstellung, wie z.B. im Internet, präsentieren. Der Datenzugriff erfolgt hier meist über eine virtuelle Benutzerrepräsentation " einen Avatar. MMVEs basieren zwar im Vergleich zu MANETs in der Regel auf physisch verlässlichen Netzen, benötigen aber aufgrund der massiven Verteilung und der großen Nutzerzahlen neue Netzwerkarchitekturen. Die Anwendungsdomäne e-Learning eignet sich in diesem Zusammenhang besonders gut für wissenschaftliche Untersuchungen, da hier eine ähnliche Entwicklung beobachtbar ist, wie bei den eingangs erwähnten Netzklassen. Genauso wie mobile Endgeräte immer kleiner und ubiquitär verfügbar werden und das Internet praktisch an jedem Ort der Welt mit hoher Bandbreite nutzbar ist, finden e-Learning Inhalte immer mehr Einzug in das tägliche Leben. Während sie früher nur eine vernachlässigbare Ergänzung zu etablierten Schulungsformen darstellten, die mehr oder weniger invasiv und starr zentral administriert wurde, steigt Ihre Bedeutung besonders im Zusammenhang mit neuen Zugangsformen täglich. Besonders das Bedürfnis an Schulen oder Universitäten sowie bei der innerbetrieblichen Aus- und Weiterbildung, immer und überall verteilt, nativ und transparent auf entsprechende Lehr- und Lerninhalte zugreifen zu können, steigt mit dem wachsenden und teilweise rein wirtschaftlich bedingten Bedarf nach einer qualitativ hohen, kontinuierlichen gesellschafts- und technikdurchdringenden Grund- und Weiterbildung. Die geforderte Transparenz und Ubiquität kann für die angesprochene Anwendungsdomäne dadurch erreicht werden, dass spezielle, auf die neuartigen verteilten Netzstrukturen abgestimmte, Applikationen entwickelt werden, die die netzinhärenten Selbstorganisations-prinzipien explizit ausnutzen. Eine wichtige Fragestellung in diesem Zusammenhang ist, welche Auswirkungen ein solcher Paradigmenwechsel auf die Qualität der Wissens-vermittlung und der Inhalte hat. Erste Evaluationen mit prototypischen Applikationen haben gezeigt, dass dieser Wechsel problemlos möglich ist. Dabei spiegeln auftretende Synergie-effekte die Abbildung auf soziale Netze wieder, die beiden Aspekten inhärent zugrunde liegt und einen Mehrwert erzeugen, der die dabei auftretenden technischen Herausforderungen und Probleme relativiert. Entsprechende Effekte lassen sich sogar noch weiter verstärken, indem kollaborative Aspekte sowohl auf Applikationsebene als auch in den darunter liegenden Basisstrukturen ausgenutzt werden. Die vorliegende Arbeit soll diese Annahmen durch adäquate Beispiele aus beiden Bereichen (MANETs und MMVEs) aus verschiedenen Perspektiven beleuchten und anhand von beispielhaften Anwendungen und darauf aufbauende Evaluationen den Synergiegewinn von e-Learning Applikationen und mögliche kollaborative Aspekte in diesem Umfeld aufzeigen.
This thesis centers on formal tree languages and on their learnability by algorithmic methods in abstractions of several learning settings. After a general introduction, we present a survey of relevant definitions for the formal tree concept as well as special cases (strings) and refinements (multi-dimensional trees) thereof. In Chapter 3 we discuss the theoretical foundations of algorithmic learning in a specific type of setting of particular interest in the area of Grammatical Inference where the task consists in deriving a correct formal description for an unknown target language from various information sources (queries and/or finite samples) in a polynomial number of steps. We develop a parameterized meta-algorithm that incorporates several prominent learning algorithms from the literature in order to highlight the basic routines which regardless of the nature of the information sources have to be run through by all those algorithms alike. In this framework, the intended target descriptions are deterministic finite-state tree automata. We discuss the limited transferability of this approach to another class of descriptions, residual finite-state tree automata, for which we propose several learning algorithms as well. The learnable class by these techniques corresponds to the class of regular tree languages. In Chapter 4we outline a recent range of attempts in Grammatical Inference to extend the learnable language classes beyond regularity and even beyond context-freeness by techniques based on syntactic observations which can be subsumed under the term 'distributional learning', and we describe learning algorithms in several settings for the tree case taking this approach. We conclude with some general reflections on the notion of learning from structural information.
Since the end of the eighties a modern and high-quality medicine is not possible without use of data processing technology and communication technology. The physician manage the enormously big volume of medical data only with the help of computer-assisted information systems. In this regard the work deals with the concept and the construction of an intranet/internet-based radiology information system. The work examine the evaluation of the radiological systems already available on market. After the analysis of relevant qualities of these systems they are measured in demands and criteria, posed before. From discovered disadvantages as for example lacking internet ability, insufficient platform independence, the major tasks of this work will be described. In the first chapter a new concept is suggested for the construction of an intranet/internet-oriented, radiological information system for the transmission and archiving of data in clinics and local physicians implemented in modular structure, producer-independent DICOM-standardization, modern, independent of platform JAVA-technology and Intranet/Internet-technology. The second chapter treats the problems of the medical image compression. After an introducing description of the known compression procedures the difficulties of the compression of the medical images is described.In accordance with these requirements the known lossy and loss-less compression-algorithms are measured. The results of the comparative examinations will get in a representative random check of more than 500 DICOM-images. Two new adaptive compression algorithms are developed by methods suggested in the work of the classification and appreciation of the quality of medical images. The third chapter is dedicated to the implementation of the components of the developed intranet/internet-oriented radiology information system. First the different net communication scenarios for the data exchange between the components of the system on the basis of Java-technology are analyzed and than an own scenario is developed. The software is developed for the visualization and processing of DICOM-image projects. The last section considers the new internet/intranet-oriented radiology information system with whose draft the scientific and practical results of this doctoral thesis were applied.
Diese Arbeit stellt eine einheitliche Workbench zur Entwicklung von mobilen Anwendungen in multihop Ad-Hoc-Netzwerken vor. Die einheitliche Workbench besteht aus drei Bausteinen: einem Simulator für diese Netzwerke, einer hybriden Emulationsumgebung für mobile multihop Ad-Hoc-Netzwerke und einer Ausführungsplattform für Anwendungen auf mobilen Geräten. Anwendungen können bereits im Simulator vollständig implementiert und evaluiert werden. Der entstandene Code kann unverändert sowohl im Emulationsteil als auch auf der Ausführungsplattform für mobile Geräte eingesetzt werden. Im passenden dreistufigen Entwicklungsprozeß wird die Anwendung im Simulator implementiert und getestet, bevor sie -- zusammen mit einer graphischen Oberfläche -- in der hybriden Emulationsumgebung weiter evaluiert und optimiert wird. Zuletzt erfolgt die Erprobung auf mobilen Geräten im Feldversuch. Mehrere tausend bis zehntausend mobile Geräte können in der Workbench durch die Beschränkung auf die topologischen Aspekte des Ad-Hoc-Netzwerks und eine besondere Bewegungsmodellabstraktion, die die besonders effiziente Berechnung der Bewegungs- und Konnektivitätsdaten der Geräte ermöglicht, effizient simuliert werden. Die Vorausberechnung und Wiederverwendung dieser Daten ist möglich. Simulationen können in Echtzeit detailliert visualisiert werden, wobei die Art der Visualisierung und das Ausgabeformat vom Benutzer definiert werden können. Die Workbench und der Softwareentwicklungsprozeß für Anwendungen in mobilen multihop Ad-Hoc-Netzwerken werden anhand einer Fallstudie erprobt. Dabei werden die Erfahrungen bei der Implementierung einer Middleware für Ad-Hoc-Anwendungen sowie bei der Entwicklung einer selbstorganisierenden Auktionsanwendung aufgezeigt.
XML (Extensible Markup Language) ist ein sequentielles Format zur Speicherung und Übermittlung strukturierter Daten. Obwohl es ursprünglich für die Dokumentenverarbeitung entwickelt wurde, findet XML heute Verwendung in nahezu allen Bereichen der Datenverarbeitung, insbesondere aber im Internet. Jede XML-Dokumentenverarbeitungs-Software basiert auf einem XML-Parser. Der Parser liest ein Dokument in XML-Syntax ein und stellt es als Dokumentbaum der eigentlichen Anwendung zur Verfügung. Dokumentenverarbeitung ist dann im wesentlichen die Manipulation von Bäumen. Moderne funktionale Programmiersprachen wie SML und Haskell unterstützen Bäume als Basis-Datentypen und sind daher besonders gut für die Implementierung von Dokumentenverarbeitungs-Systemen geeignet. Um so erstaunlicher ist es, dass dieser Bereich zum größten Teil von Java-Software dominiert wird. Dies ist nicht zuletzt darauf zurückzuführen, dass noch keine vollständige Implementierung der XML-Syntax als Parser in einer funktionalen Programmiersprache vorliegt. Eine der wichtigsten Aufgaben in der Dokumentenverarbeitung ist Querying, d.h. die Lokalisierung von Teildokumenten, die eine angegebene Strukturbedingung erfüllen und in einem bestimmten Kontext stehen. Die baumartige Auffassung von Dokumenten in XML erlaubt die Realisierung des Querying mithilfe von Techniken aus der Theorie der Baumsprachen und Baumautomaten. Allerdings müssen diese Techniken an die speziellen Anforderungen von XML angepasst werden. Eine dieser Anforderungen ist, dass auch extrem große Dokumente verarbeitet werden müssen. Deshalb sollte der Querying-Algorithmus in einem einzigen Durchlauf durch das Dokument ausführbar sein, ohne den Dokumentbaum explizit im Speicher aufbauen zu müssen. Diese Arbeit besteht aus zwei Teilen. Der erste Teil beschreibt den XML- Parser fxp, der vollständig in SML programmiert wurde. Insbesondere werden die Erfahrungen mit SML diskutiert, die während der Implementierung von fxp gewonnen wurden. Es folgt eine Analyse des Laufzeit-Verhaltens von fxp und ein Vergleich mit anderen XML-Parsern, die in imperativen oder objekt- orientierten Programmiersprachen entwickelt wurden. Im zweiten Teil beschreiben wir einen Algorithmus zum Querying von XML- Dokumenten, der auf der Theorie der Waldautomaten fundiert ist. Er findet alle Treffer einer Anfrage in höchstens zwei Durchläufen durch das Dokument. Für eine wichtige Teilklasse von Anfragen kann das Querying sogar in einem einzelnen Durchlauf realisiert werden. Außerdem wird die Implementierung des Algorithmus in SML mit Hilfe von fxp dargestellt.
Automata theory is the study of abstract machines. It is a theory in theoretical computer science and discrete mathematics (a subject of study in mathematics and computer science). The word automata (the plural of automaton) comes from a Greek word which means "self-acting". Automata theory is closely related to formal language theory [99, 101]. The theory of formal languages constitutes the backbone of the field of science now generally known as theoretical computer science. This thesis aims to introduce a few types of automata and studies then class of languages recognized by them. Chapter 1 is the road map with introduction and preliminaries. In Chapter 2 we consider few formal languages associated to graphs that has Eulerian trails. We place few languages in the Chomsky hierarchy that has some other properties together with the Eulerian property. In Chapter 3 we consider jumping finite automata, i. e., finite automata in which input head after reading and consuming a symbol, can jump to an arbitrary position of the remaining input. We characterize the class of languages described by jumping finite automata in terms of special shuffle expressions and survey other equivalent notions from the existing literature. We could also characterize some super classes of this language class. In Chapter 4 we introduce boustrophedon finite automata, i. e., finite automata working on rectangular shaped arrays (i. e., pictures) in a boustrophedon mode and we also introduce returning finite automata that reads the input, line after line, does not alters the direction like boustrophedon finite automata i. e., reads always from left to right, line after line. We provide close relationships with the well-established class of regular matrix (array) languages. We sketch possible applications to character recognition and kolam patterns. Chapter 5 deals with general boustrophedon finite automata, general returning finite automata that read with different scanning strategies. We show that all 32 different variants only describe two different classes of array languages. We also introduce Mealy machines working on pictures and show how these can be used in a modular design of picture processing devices. In Chapter 6 we compare three different types of regular grammars of array languages introduced in the literature, regular matrix grammars, (regular : regular) array grammars, isometric regular array grammars, and variants thereof, focusing on hierarchical questions. We also refine the presentation of (regular : regular) array grammars in order to clarify the interrelations. In Chapter 7 we provide further directions of research with respect to the study that we have done in each of the chapters.
Digital libraries have become a central aspect of our live. They provide us with an immediate access to an amount of data which has been unthinkable in the past. Support of computers and the ability to aggregate data from different libraries enables small projects to maintain large digital collections on various topics. A central aspect of digital libraries is the metadata -- the information that describes the objects in the collection. Metadata are digital and can be processed and studied automatically. In recent years, several studies considered different aspects of metadata. Many studies focus on finding defects in the data. Specifically, locating errors related to the handling of personal names has drawn attention. In most cases the studies concentrate on the most recent metadata of a collection. For example, they look for errors in the collection at day X. This is a reasonable approach for many applications. However, to answer questions such as when the errors were added to the collection we need to consider the history of the metadata itself. In this work, we study how the history of metadata can be used to improve the understanding of a digital library. To this goal, we consider how digital libraries handle and store their metadata. Based in this information we develop a taxonomy to describe available historical data which means data on how the metadata records changed over time. We develop a system that identifies changes to metadata over time and groups them in semantically related blocks. We found that historical meta data is often unavailable. However, we were able to apply our system on a set of large real-world collections. A central part of this work is the identification and analysis of changes to metadata which corrected a defect in the collection. These corrections are the accumulated effort to ensure data quality of a digital library. In this work, we present a system that automatically extracts corrections of defects from the set of all modifications. We present test collections containing more than 100,000 test cases which we created by extracting defects and their corrections from DBLP. This collections can be used to evaluate automatic approaches for error detection. Furthermore, we use these collections to study properties of defects. We will concentrate on defects related to the person name problem. We show that many defects occur in situations where very little context information is available. This has major implications for automatic defect detection. We also show that properties of defects depend on the digital library in which they occur. We also discuss briefly how corrected defects can be used to detect hidden or future defects. Besides the study of defects, we show that historical metadata can be used to study the development of a digital library over time. In this work, we present different studies as example how historical metadata can be used. At first we describe the development of the DBLP collection over a period of 15 years. Specifically, we study how the coverage of different computer science sub fields changed over time. We show that DBLP evolved from a specialized project to a collection that encompasses most parts of computer science. In another study we analyze the impact of user emails to defect corrections in DBLP. We show that these emails trigger a significant amount of error corrections. Based on these data we can draw conclusions on why users report a defective entry in DBLP.
Die Geschichte verteilter Systeme und Anwendungen hat die unterschiedlichsten Technologien hervorgebracht: Client-Server-Architekturen, Peer-To-Peer-Netzwerke und Komponentensysteme sind nur einige Vertreter. Die vorliegende Arbeit ist im Bereich der Middleware-Architekturen angesiedelt, einem zur Zeit sehr stark beachteten Zweig der verteilten Anwendungen. Als Mittler zwischen den Anwendungen auf der einen Seite sowie Datenbanken, eMail-Systemen oder weiterer Servern auf der anderen Seite, schlägt sie die Brücke zu heterogenen IT-Landschaften. Sie verbirgt Details und Änderungen dieser IT-Umgebungen und schafft gleichzeitig einen transparenten Zugriff auf sie. Die Forschung hat viele Technologien im Middleware-Umfeld hervorgebracht und setzt bei den Zielen unterschiedliche Schwerpunkte. Eine Sicht auf die Middleware hat den Entwickler im Fokus und soll ihn bei der Erstellung von Anwendungen und Lösungen unterstützen. Aus diesem Grund stehen hier die Schnittstellen zum Server und zur Server-Infrastruktur sowie die Einbettung der Dienste in die Middleware im Vordergrund. Der interne Aufbau sowie die inneren Datenflüsse der Middleware dienen nur der Erfüllung dieser Ziele. Eine andere Sichtweise stellt den inneren Aufbau in den Fokus der Forschung. Hier ist das Ziel die Schaffung von flexiblen und erweiterbaren Server-Strukturen sowie die Effizienz von internen Abläufen und Datenflüssen. Damit ist eine einfache Anpassung an verschiedene Einsatzumgebungen sowie die Fähigkeit, auf die Leistungsmerkmale von Clients individuell eingehen zu können, möglich. Die im Rahmen dieser Arbeit entstandene Middleware-Architektur "Smart Data Server (SDS)" setzt Konzepte um, die beide Sichtweisen miteinander kombiniert. Ein Schwerpunkt neben der Entwicklung neuer Konzepte, liegt in der praktischen Anwendbarkeit der entwickelten Middleware. Die vorliegende Arbeit zeigt, dass der Smart Data Server die Praxistauglichkeit seiner Konzepte unter realen Bedingungen unter Beweis stellen kann und zeigt gleichzeitig, welche Konstrukte für den praktischen Einsatz tatsächlich notwendig sind. Ein zweiter Schwerpunkt liegt in der Entwicklung von Mechanismen zur Abarbeitung von streamingfähigen Anfragen. Üblicherweise folgt auf die Übermittlung von Anfragen an einen Server zunächst die Berechnung einer Antwort und anschließend deren Rücktransport. Bei Streaming-Anfragen ist neben der Übermittlung von Anfrageparametern ein kontinuierlicher und in seiner Dimension nicht beschränkter Datenstrom Bestandteil der Anfrage. Der Server startet seine Berechnungen wenn möglich schon vor dem Ende der Datenübermittlung und liefert schon bei Vorliegen von Teilergebnissen diese an den Client. Der benötigte Bedarf an Speicherplatz im Server kann so optimiert werden, da nur so viele Daten der Anfrage im Server vorgehalten werden müssen wie zur Berechnung tatsächlich notwendig sind und nicht etwa die gesamte Anfrage. Die Entwicklung eines Streaming-Mechanismuses muss entsprechende Möglichkeiten in der Anfragestruktur sowie in der Architektur der Middleware vorsehen. Der Smart Data Server schafft mit der Einführung einer streamingfähigen Anfragestruktur die Voraussetzung für die Verarbeitung solcher Anfragen. Zusätzlich muss eine Server-Architektur geschaffen werden, die das Abarbeiten von Streaming-basierten Anfragen unterstützt. Hier liegt der dritte Schwerpunkt der Arbeit: die Schaffung einer flexiblen und erweiterbaren Server-Struktur sowie die Effizienz von internen Abläufen und Datenflüssen unter Berücksichtigung der Anforderung einer streamingfähigen Anfragebearbeitung. Diese Anforderungen werden mit der neu entwickelten Technologie der inneren Workflow-Programme erfüllt. Innere Workflow-Programme repräsentieren Netzwerke von hochgradig unabhängigen Serverkomponenten. Durch die Umgestaltung dieser Netze sind neue Serverstrukturen möglich, um neuen Einsatzbedingungen angepasst werden zu können. Neben diesem statischen Netzwerk von Server-Komponenten kann zur Laufzeit eine Pipeline zur Abarbeitung von Datenströmen aufgebaut werden, mit der dann letztendlich die Streamingfähigkeit des Servers hergestellt wird.