Publikationen

Is it possible to write significantly smaller formulae, when using more Boolean operators in addition to the De Morgan basis (and, or, not)? For propositional logic a negative answer was given by Pratt: every formula with additional operators can be translated to the De Morgan basis with only polynomial increase in size. Surprisingly, for modal logic the picture is different: we show that adding bi-implication allows to write exponentially smaller formulae. Moreover, we provide a complete classification of finite sets of Boolean operators showing they are either of no help (allow polynomial translations to the De Morgan basis) or can express properties as succinct as modal logic with additional bi-implication. More precisely, these results are shown for the modal logic T (and therefore for K). We complement this result showing that the modal logic S5 behaves as propositional logic: no additional Boolean operators make it possible to write significantly smaller formulae.

Lovász erkannte als einer der ersten den engen Zusammenhang zwischen der Anzahl der Subgraphen #Sub(H, G) und der Anzahl der Homomorphismen #Hom(H, G). Radu Curticapean, Holger Dell und Dániel Marx formalisierten diese Erkenntnisse unter dem Namen der ‚Graph Motif Parameter‘. Des Weit- eren zeigten sie, dass #Sub(H, G) = ∑ ρ (−1)|V (H)|−|V (Hρ )| &hahog; ∏ B∈ρ(|B| − 1)! #Aut(H) &hahog; #Hom(Hρ, G) (1) gilt [?]. In dieser Arbeit analysieren wir das Zählen von Pfaden mittels graphHom2. Wir zeigen, dass es unter gewissen Annahmen keinen Algorithmus der Laufzeit f (k)&hahog;no(&worte;k/ log(&worte;k)) für das Zählen von k-Pfaden in einem Zielgraph auf n-Ecken gibt, sofern wir graphHom2 nutzen, wobei f eine berechenbare Funktion ist die nur von k abhängt. Außerdem beweisen wir, dass Pfade, unter allen zusammenhängenden Graphen, die Anzahl der zu betrachtenden Quotientengraphen Qρ maximieren. Zudem befassen wir uns mit dem Entscheidungsproblem, Pfade in Graphen aufzufinden, und zeigen eine hinreichende Existenzbedingung für Pk ⊆ G.

The task of computing homomorphisms between two finite relational structures A and B is a well-studied question with numerous applications. Since the set Hom(A, B) of all homomorphisms may be very large having a method of representing it in a succinct way, especially one which enables us to perform efficient enumeration and counting, could be extremely useful. One simple yet powerful way of doing so is to decompose Hom(A, B) using union and Cartesian product. Such data structures, called d-representations, have been introduced by Olteanu and Závodný [Olteanu and Závodný, 2015] in the context of database theory. Their results also imply that if the treewidth of the left-hand side structure A is bounded, then a d-representation of polynomial size can be found in polynomial time. We show that for structures of bounded arity this is optimal: if the treewidth is unbounded then there are instances where the size of any d-representation is superpolynomial. Along the way we develop tools for proving lower bounds on the size of d-representations, in particular we define a notion of reduction suitable for this context and prove an almost tight lower bound on the size of d-representations of all k-cliques in a graph.

Suffixarrays sind eine der zentralen Datenstrukturen für String-Algorithmen und finden weitreichende praktische Anwendungen. Die effiziente Konstruktion dieser ist seit der ersten Veröffentlichung in 1990 ein sehr reges Forschungsgebiet geblieben. Im Jahr 2006 wurde der Algorithmus DivSufSort veröffentlicht und obwohl seitdem eine Vielzahl weiterer Suffixarray-Konstruktions-Algorithmen entwickelt wurden, konnte dieser in seiner praktischen Performanz 15 Jahre lang nicht unterboten werden. Doch im Jahr 2021 wurde ein neuer Algorithmus GSACA-DS vorgestellt, welcher unter Verwendung von speziellen Eigenschaften von Lyndon-Wörtern DivSufSort endlich in der Praxis schlagen kann. Obwohl DivSufSort solch hohe praktische Relevanz hat, entzog sich dieser bisher einer rein formellen Darstellung. GSACA-DS besitzt einen formal komplexen Ansatz, weshalb die originale Arbeit keine vollständige Grundlage für dessen Funktionsweise darstellt. Im Rahmen dieser Arbeit sollen diese Lücken in der Literatur gefüllt werden, indem beide Verfahren inklusive ihrer theoretischen Grundlagen vorgestellt, analysiert und zum ersten Mal deren Korrektheit bewiesen werden.

Die Personaleinsatzplanung ist ein komplexes Optimierungsproblem, bei dem es um die Zuteilung von Mitarbeitern zum Arbeitsplan in einer Vielzahl von Branchen geht. In dieser Arbeit betrachten wir eine spezielle Variante, die "faire" Einsatzpläne erstellen soll. Der Arbeitgeber hat, ähnlich wie bei der traditionellen Personaleinsatzplanung, die Kontrolle über die Zuweisung von Einsatzorten und Arbeitszeiten an die Arbeitnehmer. Andererseits steht es den Arbeitnehmern frei, Präferenzen für die von ihnen gewünschte Arbeit zu äußern. Durch diese Präferenzen werden die Mitarbeiter in das Planungssystem einbezogen, was sich positiv auf die Arbeitsmoral und die Produktivität auswirken soll. Ziel ist es, ein faires Planungssystem zu schaffen, das den Anforderungen des Unternehmens gerecht wird und die Arbeitswünsche der Mitarbeiter berücksichtigt. In dem in dieser Arbeit vorgeschlagenen Modell geben die Unternehmen ihren Bedarf für jeden Tag an, und die Arbeitnehmer geben ihre Präferenzen an. Unser Algorithmus versucht, einen Plan zu erstellen, der sowohl für Arbeitgeber als auch für Arbeitnehmer eine Win-Win-Situation darstellt. Um dies zu erreichen, versuchen wir, einen Zeitplan zu erstellen, der den Anforderungen des Unternehmens und den Präferenzen der Arbeitnehmer so weit wie möglich gerecht wird. Wir haben den Algorithmus mit drei verschiedenen Ansätzen implementiert. Mit allen drei Ansätzen wurden verschiedene Computerexperimente durchgeführt, und ihre Ergebnisse werden diskutiert. Unser Ansatz erstellt erfolgreich einen kurz-, mittel- und langfristigen Zeitplan, der zu einem guten Prozentsatz die Präferenzen der Mitarbeiter erfüllt.