
"Algorithmic and Computational Complexity Issues of MONET
Cuvillier Verlag eBooks
1st Edition
Published on 15. December 2008
162 pages
978-3-7369-2826-8 (ISBN)
System requirements
for PDF without DRM
E-Book Single Licence
You are acquiring a single user licence for this eBook, which you might not transfer. [L]
Available for download
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
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).
More details
Edition
1. Auflage
Language
English
Place of publication
Göttingen
Germany
File size
1,09 MB
ISBN-13
978-3-7369-2826-8 (9783736928268)
Schweitzer Classification
Other editions
Additional editions
Matthias Hagen
Algorithmic and Computational Complexity Issues of Monet
Book
12/2008
1st Edition
Cuvillier Verlag
€23.00
Article exhausted; check different version
Person
Author/originator
System requirements
File format: PDF
Copy protection: without DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook does not use copy protection or Digital Rights Management.
For more information, see our eBook Help page.