Popp, TinaReischuk, Rüdiger2023-11-092023-11-092023978-3-88579-981-8https://dl.gi.de/handle/20.500.12116/42600Reguläre Pfadabfragen sind ein wesentlicher Bestandteil von Graphabfragesprachen. Solche Abfragen betrachten einen regulären Ausdruck r und einen gerichteten, kantenbeschrifteten Graphen G und suchen nach Pfaden in G, deren Abfolge von Kantenbeschriftungen ein Wort in der Sprache von r ergibt. Um zu vermeiden, dass unendlich viele Pfade berücksichtigt werden müssen, beschränken sich Datenbank-Systeme auf Pfade ohne Wiederholungen von Knoten oder ohne Wiederholungen von Kanten. Während beliebige Pfade effizient ausgewertet und aufgezählt werden können, werden diese Probleme ohne Wiederholungen von Knoten oder Kanten schon bei sehr kleinen RPQs rechnerisch schwierig (NP-schwer). In dieser Dissertation untersuchen wir Auswertungs- und Aufzählungsprobleme unter diesen Semantiken.deText/Conference Paper