Filtern
Erscheinungsjahr
Dokumenttyp
- Dissertation (26)
- Wissenschaftlicher Artikel (3)
- Buch (Monographie) (1)
- Sonstiges (1)
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)
Institut
- Informatik (31) (entfernen)
Die eigene Web-Präsenz hat sich für Unternehmen zu einem nicht mehr wegzudenkenden Instrument, einer flexiblen Schnittstelle zum Kunden, entwickelt. Mit ihr wird eine global erreichbare Anlaufstelle offeriert: Die Chancen der Online-Techniken nutzend ist dem Unternehmen mit seiner Web-Präsenz ein Medium für die "klassische" Werbung, darüber hinaus ein Direkt-Marketing- und Dialog-Medium sowie weiterhin ein eigenes Marktforschungs-Instrument an die Hand gegeben. Dessen Entwicklung und speziell sein Betrieb stellen für ein Unternehmen in verschiedenen Hinsichten eine ernstzunehmende Herausforderung dar. Aus organisatorischer Sicht ist hier die nicht einfach zu realisierende Integration der Web-Präsenz in das Unternehmen anzustreben: Nicht einem isoliert arbeitenden, technikverliebten Mitarbeiter, dem "`Webmaster"', obliegt die Pflege der Web-Präsenz als Allein-Zuständigen, sondern entsprechend ihren Zuständigkeiten übernehmen anteilig die in den Fachabteilungen des Unternehmens tätigen Arbeitskräfte diese Aufgabe. Aus technischer Sicht stellt eine moderne Web-Präsenz ein umfangreiches, und bei hoher Dynamik entsprechend komplexes Produkt dar, für dessen Realisierung nicht unerhebliche Anstrengungen unternommen werden müssen -- insbesondere dann, wenn die zugrundeliegende Technik den organisatorischen Anforderungen innerhalb des Unternehmens gerecht werden soll. Bedingt durch die hohe Innovationsrate im Umfeld der Internet-Technologie befinden sich die Anforderungen an die Betreiber einer Web-Präsenz in einem steten Wandel und erschweren damit den Unternehmen den Einstieg in dieses Medium. Gerade die in vielen Fällen in den Unternehmen noch eingesetzten proprietären Lösungen erfordern aus technischer Sicht einen hohen Integrationsaufwand, wenn die darin vorgehaltenen Informationen für die Web-Präsenz automatisiert einer Zweitverwendung zugeführt werden sollen. Über die zusätzliche Nutzung der Unternehmens-Web-Präsenz bzw. des Systems, mit dem sie erstellt und verwaltet wird, für die unternehmensinterne Arbeit, d.h. für das Intranet, kann der für das Unternehmen entstehende Aufwand relativiert werden. In das Bild des Lebenszyklus' einer modernen Web-Präsenz eingebettet, steht die Konzeption und Entwicklung eines an die im Umfeld des Web-Präsenz-Managements in Unternehmen vorzufindenden Randbedingungen flexibel anpassbaren Online-Redaktionssystems im Vordergrund dieser Arbeit. Zentraler Bestandteil seiner Konzeption ist die Idee, ein sich aus derart vielen separaten Elementen zusammensetzendes, komplexes Gesamtdokument wie eine Unternehmens-Web-Präsenz durch eine wachsende Mitarbeiterzahl -- direkt von deren jeweiligen Arbeitsplätzen aus -- gemeinsam aufzubauen und zu pflegen. Der Praxiseinsatz des bedarfsgerecht in seinen endgültigen Ausprägungen auf die speziellen Belange der Unternehmen maßgeschneiderten Systems begründet die konsequente Nutzung von Internet-Technologien sowie die auf offenen Standards basierende Implementation durch flexible plattformunabhängige Installation und einfache Integration. Im Anschluss an ein einleitendes Kapitel beschreibt diese Arbeit ausgehend von der Problemstellung sowie technischen Grundlagen die Konzeption, Implementation und den Einsatz des webbasierten Online-Redaktionssystems bevor eine Einordnung und schließlich die Zusammenfassung den Abschluss dieser Arbeit bilden.
The visualization of relational data is at the heart of information visualization. The prevalence of visual representations for this kind of data is based on many real world examples spread over many application domains: protein-protein interaction networks in the field of bioinformatics, hyperlinked documents in the World Wide Web, call graphs in software systems, or co-author networks are just four instances of a rich source of relational datasets. The most common visual metaphor for this kind of data is definitely the node-link approach, which typically suffers from visual clutter caused by many edge crossings. Many sophisticated algorithms have been developed to layout a graph efficiently and with respect to a list of aesthetic graph drawing criteria. Relations between objects normally change over time. Visualizing the dynamics means an additional challenge for graph visualization researchers. Applying the same layout algorithms for static graphs to intermediate states of dynamic graphs may also be a strategy to compute layouts for an animated graph sequence that shows the dynamics. The major drawback of this approach is the high cognitive effort for a viewer of the animation to preserve his mental map. To tackle this problem, a sophisticated layout algorithm has to inspect the whole graph sequence and compute a layout with as little changes as possible between subsequent graphs. The main contribution and ultimate goal of this thesis is the visualization of dynamic compound weighted multi directed graphs as a static image that targets at visual clutter reduction and at mental map preservation. To achieve this goal, we use a radial space-filling visual metaphor to represent the dynamics in relational data. As a side effect the obtained pictures are very aesthetically appealing. In this thesis we firstly describe static graph visualizations for rule sets obtained by extracting knowledge from software archives under version control. In a different work we apply animated node-link diagrams to code-developer relationships to show the dynamics in software systems. An underestimated visualization paradigm is the radial representation of data. Though this kind of data has a long history back to centuries-old statistical graphics, only little efforts have been done to fully explore the benefits of this paradigm. We evaluated a Cartesian and a radial counterpart of a visualization technique for visually encoding transaction sequences and dynamic compound digraphs with both an eyetracking and an online study. We found some interesting phenomena apart from the fact that also laymen in graph theory can understand the novel approach in a short time and apply it to datasets. The thesis is concluded by an aesthetic dimensions framework for dynamic graph drawing, future work, and currently open issues.
Similarity-based retrieval of semantic graphs is a core task of Process-Oriented Case-Based Reasoning (POCBR) with applications in real-world scenarios, e.g., in smart manufacturing. The involved similarity computation is usually complex and time-consuming, as it requires some kind of inexact graph matching. To tackle these problems, we present an approach to modeling similarity measures based on embedding semantic graphs via Graph Neural Networks (GNNs). Therefore, we first examine how arbitrary semantic graphs, including node and edge types and their knowledge-rich semantic annotations, can be encoded in a numeric format that is usable by GNNs. Given this, the architecture of two generic graph embedding models from the literature is adapted to enable their usage as a similarity measure for similarity-based retrieval. Thereby, one of the two models is more optimized towards fast similarity prediction, while the other model is optimized towards knowledge-intensive, more expressive predictions. The evaluation examines the quality and performance of these models in preselecting retrieval candidates and in approximating the ground-truth similarities of a graph-matching-based similarity measure for two semantic graph domains. The results show the great potential of the approach for use in a retrieval scenario, either as a preselection model or as an approximation of a graph similarity measure.
Der vorliegende Bericht basiert auf einer universitätsweiten Online-Umfrage zum Status quo des Forschungsdatenma-nagements an der Universität Trier. Er ist ein erster Schritt, um den aktuellen und zukünftigen Bedarf an zentralen Dienstleistungen zu identifizieren. Neue Handlungsfelder sollen frühzeitig erkannt werden, auch um der Strategie-entwicklung eine Richtung zu weisen.rnDie Befragten befürworten generell die Initiative zur Entwicklung zentraler IT- und Beratungsangebote. Sie sind bereit, die eigenen Forschungsdaten anderen zur Nachnutzung zur Verfügung zu stellen, sofern die geeigneten Instrumente vorhanden, sind die eine solche Arbeitsweise unterstützen. Allerdings wird eine unkommentierte Bereit-stellung von Rohdaten eher kritisch beurteilt. Der Dokumentationsaufwand einer öffentlichen Bereitstellung von Daten wird in einem ungünstigen Kosten-Nutzenverhältnis gesehen. Es fällt auf, dass die Datenarchivierung größ-tenteils in proprietären Formaten erfolgt.
Mobile computing poses different requirements on middleware than more traditional desktop systems interconnected by fixed networks. Not only the characteristics of mobile network technologies as for example lower bandwidth and unreliability demand for customized support. Moreover, the devices employed in mobile settings usually are less powerful than their desktop counterparts. Slow processors, a fairly limited amount of memory, and smaller displays are typical properties of mobile equipment, again requiring special treatment. Furthermore, user mobility results in additional requirements on appropriate middleware support. As opposed to the quite static environments dominating the world of desktop computing, dynamic aspects gain more importance. Suitable strategies and techniques for exploring the environment e.g. in order to discover services available locally are only one example. Managing resources in a fault-tolerant manner, reducing the impact ill-behaved clients have on system stability define yet another exemplary prerequisite. Most state of the art middleware has been designed for use in the realm of static, resource rich environments and hence is not immediately applicable in mobile settings as set forth above. The work described throughout this thesis aims at investigating the suitability of different middleware technologies with regard to application design, development, and deployment in the context of mobile networks. Mostly based upon prototypes, shortcomings of those technologies are identified and possible solutions are proposed and evaluated where appropriate. Besides tailoring middleware to specific communication and device characteristics, the cellular structure of current mobile networks may and shall be exploited in favor of more scalable and robust systems. Hence, an additional topic considered within this thesis is to point out and investigate suitable approaches permitting to benefit from such cellular infrastructures. In particular, a system architecture for the development of applications in the context of mobile networks will be proposed. An evaluation of this architecture employing mobile agents as flexible, network-side representatives for mobile terminals is performed, again based upon a prototype application. In summary, this thesis aims at providing several complementary approaches regarding middleware support tailored for mobile, cellular networks, a field considered to be of rising importance in a world where mobile communication and particularly data services emerge rapidly, augmenting the globally interconnecting, wired Internet.
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.
Spatial Queues
(2000)
In the present thesis, a theoretical framework for the analysis of spatial queues is developed. Spatial queues are a generalization of the classical concept of queues as they provide the possibility of assigning properties to the users. These properties may influence the queueing process, but may also be of interest for themselves. As a field of application, mobile communication networks are modeled by spatial queues in order to demonstrate the advantage of including user properties into the queueing model. In this application, the property of main interest is the user's position in the network. After a short introduction, the second chapter contains an examination of the class of Markov-additive jump processes, including expressions for the transition probabilities and the expectation as well as laws of large numbers. Chapter 3 contains the definition and analysis of the central concept of spatial Markovian arrival processes (shortly: SMAPs) as a special case of Markov-additive jump processes, but also as a natural generalization from the well-known concept of BMAPs. In chapters 4 and 5, SMAPs serve as arrival streams for the analyzed periodic SMAP/M/c/c and SMAP/G/infinity queues, respectively. These types of queues find application as models or planning tools for mobile communication networks. The analysis of these queues involves new methods such that even for the special cases of BMAP inputs (i.e. non-spatial queues) new results are obtained. In chapter 6, a procedure for statistical parameter estimation is proposed along with its numerical results. The thesis is concluded by an appendix which collects necessary results from the theories of Markov jump processes and stochastic point fields. For special classes of Markov jump processes, new results have been obtained, too.
Due to the breath-taking growth of the World Wide Web (WWW), the need for fast and efficient web applications becomes more and more urgent. In this doctoral thesis, the emphasis will be on two concrete tasks for improving Internet applications. On the one hand, a major problem of many of today's Internet applications may be described as the performance of the Client/Server-communication: servers often take a long time to respond to a client's request. There are several strategies to overcome this problem of high user-perceived latencies; one of them is to predict future user-requests. This way, time-consuming calculations on the server's side can be performed even before the corresponding request is being made. Furthermore, in certain situations, also the pre-fetching or the pre-sending of data might be appropriate. Those ideas will be discussed in detail in the second part of this work. On the other hand, a focus will be placed on the problem of proposing hyperlinks to improve the quality of rapid written texts, at first glance, an entirely different problem to predicting client requests. Ultra-modern online authoring systems that provide possibilities to check link-consistencies and administrate link management should also propose links in order to improve the usefulness of the produced HTML-documents. In the third part of this elaboration, we will describe a possibility to build a hyperlink-proposal module based on statistical information retrieval from hypertexts. These two problem categories do not seem to have much in common. It is one aim of this work to show that there are certain, similar solution strategies to look after both problems. A closer comparison and an abstraction of both methodologies will lead to interesting synergetic effects. For example, advanced strategies to foresee future user-requests by modeling time and document aging can be used to improve the quality of hyperlink-proposals too.
Reconstructing invisible deviating events: A conformance checking approach for recurring events
(2022)
Conformance checking enables organizations to determine whether their executed processes are compliant with the intended process. However, if the processes contain recurring activities, state-of-the-art approaches unfortunately have difficulties calculating the conformance. The occurrence of complex temporal rules can further increase the complexity of the problem. Identifying this limitation, this paper presents a novel approach towards dealing with recurring activities in conformance checking. The core idea of the approach is to reconstruct the missing events in the event log using defined rules while incorporating specified temporal event characteristics. This approach then enables the use of native conformance checking algorithms. The paper illustrates the algorithmic approach and defines the required temporal event characteristics. Furthermore, the approach is applied and evaluated in a case study on an event log for melanoma surveillance.
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.
This work is concerned with two kinds of objects: regular expressions and finite automata. These formalisms describe regular languages, i.e., sets of strings that share a comparatively simple structure. Such languages - and, in turn, expressions and automata - are used in the description of textual patterns, workflow and dependence modeling, or formal verification. Testing words for membership in any given such language can be implemented using a fixed - i.e., finite - amount of memory, which is conveyed by the phrasing finite-automaton. In this aspect they differ from more general classes, which require potentially unbound memory, but have the potential to model less regular, i.e., more involved, objects. Other than expressions and automata, there are several further formalisms to describe regular languages. These formalisms are all equivalent and conversions among them are well-known.However, expressions and automata are arguably the notions which are used most frequently: regular expressions come natural to humans in order to express patterns, while finite automata translate immediately to efficient data structures. This raises the interest in methods to translate among the two notions efficiently. In particular,the direction from expressions to automata, or from human input to machine representation, is of great practical relevance. Probably the most frequent application that involves regular expressions and finite automata is pattern matching in static text and streaming data. Common tools to locate instances of a pattern in a text are the grep application or its (many) derivatives, as well as awk, sed and lex. Notice that these programs accept slightly more general patterns, namely ''POSIX expressions''. Concerning streaming data, regular expressions are nowadays used to specify filter rules in routing hardware.These applications have in common that an input pattern is specified in form a regular expression while the execution applies a regular automaton. As it turns out, the effort that is necessary to describe a regular language, i.e., the size of the descriptor,varies with the chosen representation. For example, in the case of regular expressions and finite automata, it is rather easy to see that any regular expression can be converted to a finite automaton whose size is linear in that of the expression. For the converse direction, however, it is known that there are regular languages for which the size of the smallest describing expression is exponential in the size of the smallest describing automaton.This brings us to the subject at the core of the present work: we investigate conversions between expressions and automata and take a closer look at the properties that exert an influence on the relative sizes of these objects.We refer to the aspects involved with these consideration under the titular term of Relative Descriptional Complexity.
In dieser Arbeit präsentieren wir einen systematischen Ansatz zur Multithread Implementierung von Divide und Conquer sowie inkrementellen Algorithmen. Wir stellen für beide Kategorien von Algorithmen ein Framework vor. Beide Frameworks sollen die Behandlung von Threads erleichtern, die Implementierung von parallelen Algorithmen beschleunigen und die Rechenzeit verringern. Mit Hilfe der Frameworks parallelisieren wir beispielhaft zahlreiche Algorithmen insbesondere aus dem Bereich Computational Geometry, unter anderem: Sortieralgorithmen, konvexe Hülle Algorithmen und Triangulierungen. Der Programmcode zu diese Arbeit ist in C++ unter Verwendung templatisierter Klassen implementiert und basiert auf der LEDA Bibliothek.
In dieser Arbeit wird ein Middlewaremodell für Anwendungen in mobilen ad-hoc Netzwerken vorgestellt. Der primäre Fokus liegt dabei auf Netzen, die auf Basis von mobilen Endbenutzergeräten wie PDAs, PocketPCs oder Smartphones gebildet werden und die über eine drahtlose Kommunikationstechnik wie WLAN oder Bluetooth verfügen. Zur Identifizierung der Ansprüche an eine Middleware in diesen Netzen wurden Anwendungen aus dem universitären Umfeld untersucht. Da die Kommunikation in drahtlosen Netzen nicht immer so transparent wie in drahtgebundenen Infrastrukturnetzen erfolgen kann, enthält die Middleware ein Kommunikationsframework, welches die Adaption und auch die Kombination von Kommunikationsmechanismen ermöglicht. Neben der direkten Auslieferung von Nachrichten werden auch Mechanismen zur sukzessiven Weitergabe von Nachrichten, die so genannte Store-and-Forward Kommunikation, angeboten. Hier steht insbesondere die Weitergabe von Informationen im Vorbeigehen (En-Passant) im Vordergrund. Die Komponenten der Middleware und darauf basierenden Applikationen werden als interagierende mobile Objekte modelliert. Die Interaktion dieser Objekte erfolgt aufgrund der Dynamik der mobilen ad-hoc Netze ereignisorientiert. Sowohl die Interaktion, als auch die Adaption und Wahl von Kommunikationsmechanismen erfolgt auf Basis von Informationen über das direkte Umfeld, Applikationswissen über das Netzwerk und Erfahrungen aus der Vergangenheit. Diese Informationen, die von Objekten verbreitet und gesammelt werden können, werden als Spuren bezeichnet. Da eine Aufhebung der Transparenz der Middlewarekomponenten einen höheren Entwicklungsaufwand bedeutet, wird eine Realisierung der Objektinteraktion in Objektrepräsentanten vorgeschlagen. Objektrepräsentanten ermöglichen die Kommunikation mit entfernten Objekten, das lokale Verwalten von Informationen über diese Objekte und schließlich die Repräsentierung von Objekten ohne reale Objektinstanz. Objekte ohne Objektinstanz werden verwendet, um Gerätegruppen mit bestimmten Eigenschaften zusammenzufassen, beispielsweise Objekte an einem bestimmten geographischen Ort. Somit ist auch das Wissen über geographische Orte und deren Identifizierung ein wichtiger Aspekt des Modells. Aufgrund der Anwendungsuntersuchungen ist sukzessive ein Middlewareprototyp entstanden, der in eine Simulationsumgebung für mobile ad-hoc Netze integriert ist. Die Umgebung erlaubt neben der reinen Simulation mobiler ad-hoc Netze und der zu untersuchenden Anwendung auch die Integration realer Geräte und die Ausführung der Anwendungen auf realen Geräten. Somit konnte, neben einer simulativen Untersuchung, auch eine praktische Evaluation der Anwendungen in Feldversuchen durchgeführt werden.
Even though in most cases time is a good metric to measure costs of algorithms, there are cases where theoretical worst-case time and experimental running time do not match. Since modern CPUs feature an innate memory hierarchy, the location of data is another factor to consider. When most operations of an algorithm are executed on data which is already in the CPU cache, the running time is significantly faster than algorithms where most operations have to load the data from the memory. The topic of this thesis is a new metric to measure costs of algorithms called memory distance—which can be seen as an abstraction of the just mentioned aspect. We will show that there are simple algorithms which show a discrepancy between measured running time and theoretical time but not between measured time and memory distance. Moreover we will show that in some cases it is sufficient to optimize the input of an algorithm with regard to memory distance (while treating the algorithm as a black box) to improve running times. Further we show the relation between worst-case time, memory distance and space and sketch how to define "the usual" memory distance complexity classes.
This thesis considers the general task of computing a partition of a set of given objects such that each set of the partition has a cardinality of at least a fixed number k. Among such kinds of partitions, which we call k-clusters, the objective is to find the k-cluster which minimises a certain cost derived from a given pairwise difference between objects which end up the same set. As a first step, this thesis introduces a general problem, denoted by (||.||,f)-k-cluster, which models the task to find a k-cluster of minimum cost given by an objective function computed with respect to specific choices for the cost functions f and ||.||. In particular this thesis considers three different choices for f and also three different choices for ||.|| which results in a total of nine different variants of the general problem. Especially with the idea to use the concept of parameterised approximation, we first investigate the role of the lower bound on the cluster cardinalities and find that k is not a suitable parameter, due to remaining NP-hardness even for the restriction to the constant 3. The reductions presented to show this hardness yield the even stronger result which states that polynomial time approximations with some constant performance ratio for any of the nine variants of (||.||,f)-k-cluster require a restriction to instances for which the pairwise distance on the objects satisfies the triangle inequality. For this restriction to what we informally refer to as metric instances, constant-factor approximation algorithms for eight of the nine variants of (||.||,f)-k-cluster are presented. While two of these algorithms yield the provably best approximation ratio (assuming P!=NP), others can only guarantee a performance which depends on the lower bound k. With the positive effect of the triangle inequality and applications to facility location in mind, we discuss the further restriction to the setting where the given objects are points in the Euclidean metric space. Considering the effect of computational hardness caused by high dimensionality of the input for other related problems (curse of dimensionality) we check if this is also the source of intractability for (||.||,f)-k-cluster. Remaining NP-hardness for restriction to small constant dimensionality however disproves this theory. We then use parameterisation to develop approximation algorithms for (||.||,f)-k-cluster without restriction to metric instances. In particular, we discuss structural parameters which reflect how much the given input differs from a metric. This idea results in parameterised approximation algorithms with parameters such as the number of conflicts (our name for pairs of objects for which the triangle inequality is violated) or the number of conflict vertices (objects involved in a conflict). The performance ratios of these parameterised approximations are in most cases identical to those of the approximations for metric instances. This shows that for most variants of (||.||,f)-k-cluster efficient and reasonable solutions are also possible for non-metric instances.
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.
Hardware bugs can be extremely expensive, financially. Because microprocessors and integrated circuits have become omnipresent in our daily live and also because of their continously growing complexity, research is driven towards methods and tools that are supposed to provide higher reliability of hardware designs and their implementations. Over the last decade Ordered Binary Decision Diagrams (OBDDs) have been well proven to serve as a data structure for the representation of combinatorial or sequential circuits. Their conciseness and their efficient algorithmic properties are responsible for their huge success in formal verification. But, due to Shannon's counting argument, OBDDs can not always guarantee the concise representation of a given design. In this thesis, Parity Ordered Binary Decision Diagrams are presented, which are a true extension of OBDDs. In addition to the regular branching nodes of an OBDD, functional nodes representing a parity operation are integrated into the data structure, thus resulting in Parity-OBDDs. Parity-OBDDs are more powerful than OBDDs are, but, they are no longer a canonical representation. Besides theoretical aspects of Parity-OBDDs, algorithms for their efficient manipulation are the main focus of this thesis. Furthermore, an analysis on the factors that influence the Parity-OBDD representation size gives way for the development of heuristic algorithms for their minimization. The results of these analyses as well as the efficiency of the data structure are also supported by experiments. Finally, the algorithmic concept of Parity-OBDDs is extended to Mod-p-Decision Diagrams (Mod-p-DDs) for the representation of functions that are defined over an arbitrary finite domain.
Today, usage of complex circuit designs in computers, in multimedia applications and communication devices is widespread and still increasing. At the same time, due to Moore's Law we do not expect to see an end in the growth of the complexity of digital circuits. The decreasing ability of common validation techniques -- like simulation -- to assure correctness of a circuit design enlarges the need for formal verification techniques. Formal verification delivers a mathematical proof that a given implementation of a design fulfills its specification. One of the basic and during the last years widely used data structure in formal verification are the so called Ordered Binary Decision Diagrams (OBDDs) introduced by R. Bryant in 1986. The topic of this thesis is integration of structural high-level information in the OBDD-based formal verification of sequential systems. This work consist of three major parts, covering different layers of formal verification applications: At the application layer, an assertion checking methodology, integrated in the verification flow of the high-level design and verification tool Protocol Compiler is presented. At the algorithmic layer, new approaches for partitioning of transition relations of complex finite state machines, that significantly improve the performance of OBDD-based sequential verification are introduced. Finally, at the data structure level, dynamic variable reordering techniques that drastically reduce the time required for reordering without a trade-off in OBDD-size are described. Overall, this work demonstrates how a tighter integration of applications by using structural information can significantly improve the efficiency of formal verification applications in an industrial setting.