The dissertation thesis studies the complexity of membership problems. Generally, membership problems consider the question whether a given object belongs to a set. Object and set are part of the input. The thesis studies the complexity of membership problems for two special kinds of sets. The first problem class asks whether a given natural number belongs to a set of natural numbers. The set of natural numbers is defined via finite recurrent systems: sets are built by iterative application of operations, like union, intersection, complementation and arithmetical operations, to already defined sets. This general problem implies further problems by restricting the set of used operations. The thesis contains completeness results for well-known complexity classes as well as undecidability results for these problems. The second problem class asks whether a given graph is a minimal triangulation of another graph. A graph is a triangulation of another graph, if it is a chordal spanning supergraph of the second graph. If no proper supergraph of the first graph is a triangulation of the second graph, the first graph is a minimal triangulation of the second graph. The complexity of the membership problem for minimal triangulations of several graph classes is investigated. Restricted variants are solved by linear-time algorithms. These algorithms rely on appropriate characterisations of minimal triangulations. / Die Dissertation beschäftigt sich mit der Komplexität von Enthaltenseinproblemen. Allgemein gesprochen, interessieren sich Enthaltenseinprobleme für die Frage, ob ein gegebenes Objekt zu einer Menge gehört. Sowohl Objekt als auch Menge sind Teil der Eingabe. Die Arbeit untersucht die Komplexität dieser Fragestellung für zwei konkrete Mengenklassen. Zum ersten soll entschieden werden, ob eine natürliche Zahl zu einer Menge natürlicher Zahlen gehört. Entscheidend für die Komplexität dieses Problems ist die Darstellung der Menge natürlicher Zahlen. Es werden rekurrente Systeme verwendet, die Mengen natürlicher Zahlen durch iterierte Anwendung einfacher Operationen, wie die drei Mengenoperationen Vereinigung, Durchschnitt, Komplementbildung und arithmetische Operationen, auf bereits konstruierte Mengen definieren. Beschränkt man die Menge verwendeter Operationen, ergibt sich eine Vielzahl von Problemen, deren Komplexitäten bestimmt werden. Es werden Vollständigkeitsresultate für bekannte Komplexitätsklassen wie auch Unentscheidbarkeit gezeigt. Zum zweiten soll entschieden werden, ob ein Graph eine minimale Triangulation eines anderen Graphen ist. Ein Graph ist Triangulation eines anderen Graphen, wenn er ein chordaler aufspannender Obergraph des zweiten Graphen ist. Ist kein echter Obergraph des ersten Graphen eine Triangulation des zweiten Graphen, so ist der erste Graph eine minimale Triangulation des zweiten Graphen. Ein Graph kann mehrere minimale Triangulationen besitzen. Untersucht wird die Komplexität des Enthaltenseinproblems für minimale Triangulationen für verschiedene Graphenklassen, und es werden Linearzeitalgorithmen zur Lösung einer eingeschränkten Variante des jeweiligen Problems angegeben. Die Algorithmen basieren alle auf geeigneten Charakterisierungen minimaler Triangulationen.
| Identifer | oai:union.ndltd.org:uni-wuerzburg.de/oai:opus.bibliothek.uni-wuerzburg.de:1626 |
| Date | January 2006 |
| Creators | Meister, Daniel |
| Source Sets | University of Würzburg |
| Language | English |
| Detected Language | German |
| Type | doctoralthesis, doc-type:doctoralThesis |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0174 seconds