München, Techn. Univ., Diss., 2010.

Vollständig reguläre Halbgruppen weisen eine stark regelmäßige Struktur auf, die verschiedenste Zerlegungsmöglichkeiten gestatten. Ziel dieser Dissertation ist es, diese strukturelle Regelmäßigkeit auf Halbringe zu übertragen und die gewonnenen Algebren zu untersuchen. Mehrere Charakterisierungen werden herausgearbeitet, aufgrund derer es sich herausstellt, dass die Klasse aller vollständig regulären Halbringe eine Varietät bilden, deren Untervarietäten in der Folge untersucht werden. Zentrale Bedeutung haben dabei vollständig einfache Halbringe, deren Analyse einen der Schwerpunkte der Arbeit darstellt. Es zeigt sich, dass diese Bausteine vollständig regulärer Halbringe untereinander eine feste Struktur besitzen, selber aber auch als Zusammensetzung von isomorphen Halbringen aufgefasst werden können. Außerdem werden orthodoxe Halbringe, also Halbringe, deren idempotente Elemente einen Unterhalbring bilden, betrachtet. Zunächst wird dabei wieder auf mehrere Teilklassen eingegangen, bevor abschließend für beliebige vollständig reguläre Halbringe eine Beschreibung der kleinsten Kongruenz angegeben wird, deren Faktorhalbring orthodox ist.

Die Arbeit beschäftigt sich mit fast-idempotenten Halbringen, die eine Verallgemeinerung der idempotenten Halbringe darstellen. Es werden - ausgehend von Halbringen mit zwei Elementen - bis auf isomorphe Bilder sämtliche fast-idempotente Halbringe mit drei Elementen generiert, diejenigen Halbringe, die schon in durch zweielementige Halbringe erzeugten Varietäten liegen, aussortiert und die in den verbleibenden elf Halbringen gültigen Gleichungen charakterisiert. Der Verband L(IA3) der Varietäten generiert durch fast-idempotente Halbringe mit maximal drei Elementen wird mit Hilfe eines Kontexts mit 21 Halbringen als Attribute und 28 trennenden Gleichungen als Objekte vollständig bestimmt und besteht aus 19.901 Varietäten. Im Anschluss richtet sich der Fokus der Arbeit auf den Verband L(IA) der fast-idempotenten Halbringe. In diesem werden insbesondere die Varietät V = [xy = yx, xy = xy+x] und deren Untervarietäten V_k = [x^k = x^(k+1)], k >= 2; untersucht. Für all diese Varietäten wird jeweils eine Konstruktionsmethode für eine abzählbare Kette an Untervarietäten der gegebenen Varietät eingeführt und somit schließlich gezeigt, dass der Verband L(IA) aus mindestens abzählbar unendlich vielen Varietäten besteht.

Die Arbeit beschäftigt sich mit fast-idempotenten Halbringen, die eine Verallgemeinerung der idempotenten Halbringe darstellen. Es werden - ausgehend von Halbringen mit zwei Elementen - bis auf isomorphe Bilder sämtliche fast-idempotente Halbringe mit drei Elementen generiert, diejenigen Halbringe, die schon in durch zweielementige Halbringe erzeugten Varietäten liegen, aussortiert und die in den verbleibenden elf Halbringen gültigen Gleichungen charakterisiert. Der Verband L(IA3) der Varietäten generiert durch fast-idempotente Halbringe mit maximal drei Elementen wird mit Hilfe eines Kontexts mit 21 Halbringen als Attribute und 28 trennenden Gleichungen als Objekte vollständig bestimmt und besteht aus 19.901 Varietäten. Im Anschluss richtet sich der Fokus der Arbeit auf den Verband L(IA) der fast-idempotenten Halbringe. In diesem werden insbesondere die Varietät V = [xy = yx, xy = xy+x] und deren Untervarietäten V_k = [x^k = x^(k+1)], k >= 2; untersucht. Für all diese Varietäten wird jeweils eine Konstruktionsmethode für eine abzählbare Kette an Untervarietäten der gegebenen Varietät eingeführt und somit schließlich gezeigt, dass der Verband L(IA) aus mindestens abzählbar unendlich vielen Varietäten besteht.

Ulm, Univ., Diss., 2007.

Vollständig reguläre Halbgruppen weisen eine stark regelmäßige Struktur auf, die verschiedenste Zerlegungsmöglichkeiten gestatten. Ziel dieser Dissertation ist es, diese strukturelle Regelmäßigkeit auf Halbringe zu übertragen und die gewonnenen Algebren zu untersuchen. Mehrere Charakterisierungen werden herausgearbeitet, aufgrund derer es sich herausstellt, dass die Klasse aller vollständig regulären Halbringe eine Varietät bilden, deren Untervarietäten in der Folge untersucht werden. Zentrale Bedeutung haben dabei vollständig einfache Halbringe, deren Analyse einen der Schwerpunkte der Arbeit darstellt. Es zeigt sich, dass diese Bausteine vollständig regulärer Halbringe untereinander eine feste Struktur besitzen, selber aber auch als Zusammensetzung von isomorphen Halbringen aufgefasst werden können. Außerdem werden orthodoxe Halbringe, also Halbringe, deren idempotente Elemente einen Unterhalbring bilden, betrachtet. Zunächst wird dabei wieder auf mehrere Teilklassen eingegangen, bevor abschließend für beliebige vollständig reguläre Halbringe eine Beschreibung der kleinsten Kongruenz angegeben wird, deren Faktorhalbring orthodox ist.

Eine der stärksten Erweiterungen der klassischen Theorie formaler Sprachen und Automaten ist die Einbeziehung von Gewichten oder Vielfachheiten aus einem Halbring. Diese Dissertation untersucht gewichtete Automaten über Strukturen mit Nebenläufigkeit. Wir erweitern die Arbeit von Lodaya und Weil und erhalten so ein Modell gewichteter verzweigender Automaten, in dem die Berechnung des Gewichts einer parallelen Komposition anders als die einer sequentiellen Komposition gehandhabt wird. Die von Lodaya und Weil eingeführten Automaten modellieren Nebenläufigkeit durch Verzweigen. Ein verzweigender Automat ist ein endlicher Automat mit drei verschiedenen Typen von Transitionen. Sequentielle Transitionen überführen durch Ausführen eines Ereignisses einen Zustand in einen anderen. Dagegen sind Gabel- und Binde-Transitionen für das Verzweigen verantwortlich. Läufe dieser Automaten werden beschrieben durch sequentiell-parallele posets, kurz sp-posets. Alle Transitionen des Automaten werden in unserem Modell mit Gewichten versehen. Neben dem Nichtdeterminismus und der sequentiellen Komposition wollen wir nun auch die parallele Komposition quantitativ behandeln. Dafür benötigen wir eine Gewichtsstruktur mit einer Addition, einer sequentiellen und einer parallelen Multiplikation. Solch eine Struktur, genannt Bihalbring, besteht damit de facto aus zwei Halbringen mit derselben additiven Struktur. Weiterhin muss die parallele Multiplikation kommutativ sein. Das Verhalten eines gewichteten verzweigenden Automaten ist dann eine Funktion, die jeder sp-poset ein Element eines Bihalbrings zuordnet. Das Hauptresultat charakterisiert das Verhalten dieser Automaten im Sinne von Kleenes und Schützenbergers Sätzen über das Zusammenfallen der Klassen der erkennbaren und der rationalen Sprachen bzw. formalen Potenzreihen. Darüber hinaus untersuchen wir den Abschluss dieser Verhalten unter allen rationalen Operationen und unter dem Hadamard-Produkt. Letztlich diskutieren wir Zusammenhänge zwischen Reihen und Sprachen im Rahmen verzweigender Automaten. / One of the most powerful extensions of classical formal language and automata theory is the consideration of weights or multiplicities from a semiring. This thesis investigates weighted automata over structures incorporating concurrency. Extending work by Lodaya and Weil, we propose a model of weighted branching automata in which the calculation of the weight of a parallel composition is handled differently from the calculation of the weight of a sequential composition. The automata as proposed by Lodaya and Weil model concurrency by branching. A branching automaton is a finite-state device with three different types of transitions. Sequential transitions transform a state into another one by executing an action. In contrast, fork and join transitions are responsible for branching. Executions of such systems can be described by sequential-parallel posets, or sp-posets for short. In the model considered here all kinds of transitions are equipped with weights. Beside non-determinism and sequential composition we would like to deal with the parallel composition in a quantitative way. Therefore, we are in need of a weight structure equipped with addition, a sequential, and, moreover, a parallel multiplication. Such a structure, called a bisemiring, is actually composed of two semirings with the same additive structure. Moreover, the parallel multiplication has to be commutative. Now, the behavior of a weighted branching automaton is a function that associates with every sp-poset an element from the bisemiring. The main result characterizes the behavior of these automata in the spirit of Kleene's and Schützenberger's theorems about the coincidence of recognizable and rational languages, and formal power series, respectively. Moreover, we investigate the closure of behaviors under all rational operations and under Hadamard-product. Finally, we discuss connections between series and languages within our setting.

Eine der stärksten Erweiterungen der klassischen Theorie formaler Sprachen und Automaten ist die Einbeziehung von Gewichten oder Vielfachheiten aus einem Halbring. Diese Dissertation untersucht gewichtete Automaten über Strukturen mit Nebenläufigkeit. Wir erweitern die Arbeit von Lodaya und Weil und erhalten so ein Modell gewichteter verzweigender Automaten, in dem die Berechnung des Gewichts einer parallelen Komposition anders als die einer sequentiellen Komposition gehandhabt wird. Die von Lodaya und Weil eingeführten Automaten modellieren Nebenläufigkeit durch Verzweigen. Ein verzweigender Automat ist ein endlicher Automat mit drei verschiedenen Typen von Transitionen. Sequentielle Transitionen überführen durch Ausführen eines Ereignisses einen Zustand in einen anderen. Dagegen sind Gabel- und Binde-Transitionen für das Verzweigen verantwortlich. Läufe dieser Automaten werden beschrieben durch sequentiell-parallele posets, kurz sp-posets. Alle Transitionen des Automaten werden in unserem Modell mit Gewichten versehen. Neben dem Nichtdeterminismus und der sequentiellen Komposition wollen wir nun auch die parallele Komposition quantitativ behandeln. Dafür benötigen wir eine Gewichtsstruktur mit einer Addition, einer sequentiellen und einer parallelen Multiplikation. Solch eine Struktur, genannt Bihalbring, besteht damit de facto aus zwei Halbringen mit derselben additiven Struktur. Weiterhin muss die parallele Multiplikation kommutativ sein. Das Verhalten eines gewichteten verzweigenden Automaten ist dann eine Funktion, die jeder sp-poset ein Element eines Bihalbrings zuordnet. Das Hauptresultat charakterisiert das Verhalten dieser Automaten im Sinne von Kleenes und Schützenbergers Sätzen über das Zusammenfallen der Klassen der erkennbaren und der rationalen Sprachen bzw. formalen Potenzreihen. Darüber hinaus untersuchen wir den Abschluss dieser Verhalten unter allen rationalen Operationen und unter dem Hadamard-Produkt. Letztlich diskutieren wir Zusammenhänge zwischen Reihen und Sprachen im Rahmen verzweigender Automaten. / One of the most powerful extensions of classical formal language and automata theory is the consideration of weights or multiplicities from a semiring. This thesis investigates weighted automata over structures incorporating concurrency. Extending work by Lodaya and Weil, we propose a model of weighted branching automata in which the calculation of the weight of a parallel composition is handled differently from the calculation of the weight of a sequential composition. The automata as proposed by Lodaya and Weil model concurrency by branching. A branching automaton is a finite-state device with three different types of transitions. Sequential transitions transform a state into another one by executing an action. In contrast, fork and join transitions are responsible for branching. Executions of such systems can be described by sequential-parallel posets, or sp-posets for short. In the model considered here all kinds of transitions are equipped with weights. Beside non-determinism and sequential composition we would like to deal with the parallel composition in a quantitative way. Therefore, we are in need of a weight structure equipped with addition, a sequential, and, moreover, a parallel multiplication. Such a structure, called a bisemiring, is actually composed of two semirings with the same additive structure. Moreover, the parallel multiplication has to be commutative. Now, the behavior of a weighted branching automaton is a function that associates with every sp-poset an element from the bisemiring. The main result characterizes the behavior of these automata in the spirit of Kleene's and Schützenberger's theorems about the coincidence of recognizable and rational languages, and formal power series, respectively. Moreover, we investigate the closure of behaviors under all rational operations and under Hadamard-product. Finally, we discuss connections between series and languages within our setting.