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.

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.

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.

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.

Many real-life phenomena, such as computer systems, communication networks, manufacturing systems, supermarket checkout lines as well as structural military systems can be represented by means of queueing models. Looking at queueing models, a controller may considerably improve the system's performance by reducing queue lengths, or increasing the throughput, or diminishing the overhead, whereas in the absence of a controller the system behavior may get quite erratic, exhibiting periods of high load and long queues followed by periods, during which the servers remain idle. The theoretical foundations of controlled queueing systems are led in the theory of Markov, semi-Markov and semi-regenerative decision processes. In this thesis, the essential work consists in designing controlled queueing models and investigation of their optimal control properties for the application in the area of the modern telecommunication systems, which should satisfy the growing demands for quality of service (QoS). For two types of optimization criterion (the model without penalties and with set-up costs), a class of controlled queueing systems is defined. The general case of the queue that forms this class is characterized by a Markov Additive Arrival Process and heterogeneous Phase-Type service time distributions. We show that for these queueing systems the structural properties of optimal control policies, e.g. monotonicity properties and threshold structure, are preserved. Moreover, we show that these systems possess specific properties, e.g. the dependence of optimal policies on the arrival and service statistics. In order to practically use controlled stochastic models, it is necessary to obtain a quick and an effective method to find optimal policies. We present the iteration algorithm which can be successfully used to find an optimal solution in case of a large state space.