"Algorithmic and Computational Complexity Issues of MONET

Autor(en): Hagen, Matthias Universität Jena, 15. Dezember 2008 Seiten: 162 Auflage: 1 Aufl. Sprache: EN ISBN-10: 3867278261 ISBN-13: 9783867278263 Zugeordnete Fachbereiche: Mathematik | Informatik Kategorie: Dissertation Bezugsmöglichkeiten Print Version 23,00 € 19,55 € In den Warenkorb eBook (1090.5 kB) 23,00 € In den Warenkorb

Kurzbeschreibung

In dieser Dissertation beschäftigen wir uns mit dem Problem Monet – ein englisches Akronym für Mo(notone) n(ormal form) e(quivalence) t(est). Die Problemstellung bei Monet ist, die Äquivalenz einer monotonen disjunktiven Normalform . und einer monotonen konjunktiven Normalform ψ zu entscheiden. Dies ist eigentlich ein Abdeckungsproblem und kann ebenso als das Aufzählen aller (in einem gewissen Sinne) minimalen Lösungen irgendeines Systems interpretiert
werden. Deswegen gibt es auch eine Vielzahl sehr ähnlicher Fragestellungen aus unterschiedlichsten Anwendungsgebieten. Unsere Resultate können grob in zwei Gruppen eingeteilt werden. Zum einen gibt es Resultate, die den Entwurf und die Analyse von Algorithmen betreten,
zum anderen sind Resultate enthalten, die eher Komplexitätsaspekte des Problems berühren. Im algorithmischen Teil geben wir untere Schranken für einige Algorithmen an und berichten über Resultate von praktischen Untersuchungen des theoretisch schnellsten Algorithmus in Experimenten. Im eher komplexitätstheoretischeren Teil dieser Dissertation zeigen wir für erschiedene eingeschränkte Klassen des Problems, dass sie sich mit logarithmischem Platzbedarf lösen lassen. Dadurch verbessern wir den Ressourcenbedarf gegenüber den vorher bekannten Polynomialzeitschranken. Darüber hinaus ordnen wir Monet für verschiedene Parameter in die Klasse der festparameter-handhabbaren Probleme ein. Im Einzelnen beweisen wir die folgenden Hauptergebnisse unter Zuhilfenahme einer breiten Palette von algorithmischen und komplexitätstheoretischen Techniken.
. Verschiedene eingeschränkte Klassen des Problems Monet lassen sich mit
logarithmischem Speicherplatzbedarf lösen. Dazu gehören die Klassen bei
denen die DNF

– nur eine konstante Anzahl Monome enthält (Abschnitt 4.1.1), nur Monome
konstanter Größe enthält (Abschnitt 4.1.2), nur Monome enthält, die jeweils nur höchstens konstant viele Variablen nicht enthalten (Abschnitt 4.1.3),
– regulär (Abschnitt 4.2.1), ausgerichtet (Abschnitt 4.2.2), oder 2-monoton
(Abschnitt 4.2.3) ist.
-Weder der DL-Algorithmus (Abschnitt 5.1.2), noch der BMR- Algorithmus
(Abschnitt 5.1.3), noch der KS-Algorithmus (Abschnitt 5.1.4), noch der
HBC-Algorithmus (Abschnitt 5.2) für das Problem Monet laufen in Polynomialzeit bezüglich der Ein- und Ausgabegröße. Die Laufzeit der Algorithmen ist jeweils mindestens nÙ(log log n), wobei n die Größe der Ein- und Ausgabe ist.
-Der FK-Algorithmus B für das Problem Monet erweist sich in praktischen
Experimenten auf vielen Eingaben als konkurrenzfähig zum FK-Algorithmus
A (Kapitel 6).
-Monet ist festparameter-handhabbar für die Parameter – Anzahl v der Variablen in . und ψ (Abschnitt 7.1),
– Anzahl m der Monome in . (Abschnitt 7.2),– einen Parameter q, der die Variablenhäufigkeiten in . beschreibt (Abschnitt 7.3), und einen Parameter, der die Größe der Vereinigungen von Transversalen bzw. Kanten des Hypergraphen der DNF . angibt (Abschnitt 7.4.3). Diese Dissertation enthält Material, das in den Zeitschriften Discrete Applied Mathematics,
Information and Computation und Information Processing Letters erschienen ist bzw. erscheinen wird, sowie Material, das auf der Konferenz
”Mathematical Foundations of Computer Science“ (MFCS 2005), und den Workshops ”Graph-Theoretic Concepts in Computer Science“ (WG 2007),
”Parameterized and Exact Computation“ (IWPEC 2008) und
”Workshop on Algorithm Engineering & Experiments“ (ALENEX 2009) vorgestellt und in den entsprechenden
Tagungsbänden veröffentlicht wurde bzw. wird.

Description

In this thesis, we study the problem Monet—the Mo(notone) n(ormal form)
e(quivalence) t(est)—that asks to decide equivalence of a monotone disjunctive normal form . and a monotone conjunctive normal form ψ. This problem is a covering problem that can be interpreted as the task of enumerating all (in some sense) minimal solutions of some system. Hence, there is a huge number of similar questions in many problems from diverse applications.Our results can roughly be divided into results on the design and evaluation of algorithms for Monet and results that rather touch complexity questions related to the problem. As for the algorithmic part, we will give lower bounds for several known algorithms and report results obtained by practically examining the theoretically
fastest algorithm in computational experiments. As for the complexity
part of this thesis, we show several restricted classes of the problem to be solvable in logarithmic space, which improves previously known polynomial time bounds. We also show Monet to be in the complexity class of .xed-arameter tractable problems with respect to several parameters. More precisely, we prove the following main results using various algorithmic and computational complexity techniques. - Several restricted classes of Monet are solvable in logarithmic space. In
particular, these are the classes where the DNF– contains only a constant number of monomials (Section 4.1.1), contains only monomials of constant size (Section 4.1.2), contains only monomials that each do not contain only a constant number of variables
(Section 4.1.3),- is regular (Section 4.2.1), aligned (Section 4.2.2), or 2-monotonic (Section 4.2.3).- The DL-algorithm (Section 5.1.2), the BMR-algorithm (Section 5.1.3), the KS-algorithm (Section 5.1.4), and the HBC-algorithm (Section 5.2) for the
problem Monet are not output-polynomial. Their running times are at
least nÙ(log log n), where n denotes the size of the input and output.-FK-algorithm B for the problem Monet is experimentally competitive to FK-algorithm A on many classes (Chapter 6).-Monet is .xed-parameter tractable with respect to the parameters
– number v of variables in . and ψ (Section 7.1),
– number m of monomials in . (Section 7.2),
– a parameter q describing the variable frequencies in . (Section 7.3),
– and a parameter bounding the unions of transversals or edges of .’s
associated hypergraph (Section 7.4.3).
This thesis contains material (to be) published in the journals Discrete Applied Mathematics, Information and Computation and Information Processing Letters, as well as material (to be) presented at, and (to be) published in the proceedings
of, the conference “Mathematical Foundations of Computer Science” (MFCS 2005), and the workshops “Graph-Theoretic Concepts in Computer Science” (WG 2007), “Parameterized and Exact Computation” (IWPEC 2008) and “Workshop on Algorithm Engineering & Experiments” (ALENEX 2009).