Departments  

Book Series (82) 
1138

Medienwissenschaften 
15

Humanities 
2088

Natural Sciences 
5194

Mathematics  221 
Informatics  301 
Physics  968 
Chemistry  1313 
Geosciences  125 
Human medicine  232 
Stomatology  10 
Veterinary medicine  88 
Pharmacy  144 
Biology  794 
Biochemistry, molecular biology, gene technology  108 
Biophysics  24 
Domestic and nutritional science  43 
Agricultural science  971 
Forest science  198 
Horticultural science  16 
Environmental research, ecology and landscape conservation  137 
Geographie 
1

Engineering 
1612

Common 
83

Leitlinien Unfallchirurgie
5. Auflage bestellen 
Table of Contents, Datei (48 KB)
Extract, Datei (120 KB)
ISBN13 (Printausgabe)  3867278261 
ISBN13 (Hard Copy)  9783867278263 
ISBN13 (eBook)  9783736928268 
Language  English 
Page Number  162 
Edition  1 Aufl. 
Volume  0 
Publication Place  Göttingen 
Place of Dissertation  Universität Jena 
Publication Date  20081215 
General Categorization  Dissertation 
Departments 
Mathematics
Informatics 
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 .xedarameter 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 2monotonic (Section 4.2.3). The DLalgorithm (Section 5.1.2), the BMRalgorithm (Section 5.1.3), the KSalgorithm (Section 5.1.4), and the HBCalgorithm (Section 5.2) for the
problem Monet are not outputpolynomial. Their running times are at
least nÙ(log log n), where n denotes the size of the input and output.FKalgorithm B for the problem Monet is experimentally competitive to FKalgorithm A on many classes (Chapter 6).Monet is .xedparameter 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 “GraphTheoretic Concepts in Computer Science” (WG 2007), “Parameterized and Exact Computation” (IWPEC 2008) and “Workshop on Algorithm Engineering & Experiments” (ALENEX 2009).