Publications/Technical Reports
Research Papers
- Sieling, D. and Wegener, I. (1993).
Reduction of OBDDs in linear time.
Information Processing Letters 48(3), 139-144.
- Sieling, D. and Wegener, I. (1993).
NC-algorithms for operations on binary decision diagrams.
Parallel Processing Letters 3(1), 3-12.
- Sieling, D. and Wegener, I. (1995).
New lower bounds and hierarchy results for restricted branching
programs.
Proceedings of Workshop on Graph-Theoretic Concepts in Computer Science
WG'94, Lecture Notes in Computer Science 903, Springer, 359-370.
- Sieling, D. and Wegener, I. (1995).
Graph driven BDDs - A new data structure for Boolean functions.
Theoretical Computer Science 141, 283-310.
- Sieling, D. (1996).
New lower bounds and hierarchy results for restricted branching
programs.
Journal of Computer and System Sciences 53(1), 79-87.
- Sieling, D. (1996).
Variable orderings and the size of OBDDs for partially symmetric
Boolean
functions.
Proceedings of the Synthesis And System Integration of Mixed
Technologies
(SASIMI'96), 189-196.
- Sieling, D. and Wegener, I. (1998).
On the representation of partially symmetric Boolean functions by
ordered
multiple valued decision diagrams.
Multiple Valued Logic 4, 63-96.
- Sieling, D. (1998).
Variable orderings and the size of OBDDs for random partially symmetric
Boolean functions.
Random Structures & Algorithms 13, 49-70.
- Drechsler, R., Sauerhoff, M. and Sieling, D. (1998).
The complexity of the inclusion operation on OFDDs.
IEEE Transactions on Computer-Aided Design 17(5), 457-459.
- Bollig, B., Sauerhoff, M., Sieling, D. and Wegener, I. (1998).
Hierarchy theorems for kOBDDs and kIBDDs.
Theoretical Computer Science 205, 45-60.
- Sieling, D. (1998).
On the existence of polynomial time approximation schemes for OBDD
minimization (extended abstract).
Proceedings of 15th Symposium on Theoretical Aspects of Computer
Science
STACS'98, Lecture Notes in Computer Science 1373, Springer, 205-215.
- Löbbing, M., Sieling, D. and Wegener, I. (1998).
Parity OBDDs cannot be handled efficiently enough.
Information Processing Letters 67, 163-168.
- Sieling, D. (1999).
The complexity of minimizing FBDDs.
Proceedings of 24th Symposium on Mathematical Foundations of Computer
Science MFCS, Lecture Notes in Computer Science 1672, 251-261.
- Sieling, D. (1999).
Lower bounds for linear transformed OBDDs and FBDDs.
Proceedings of Conference on the Foundations of Software Technology
and Theoretical Computer Science FST&TCS, Lecture Notes in Computer
Science 1738, 356-368.
- Savický, P. and Sieling, D. (2000).
A hierarchy result for read-once branching programs with restricted
parity nondeterminism (extended abstract).
Proceedings of 25th Symposium on Mathematical Foundations of Computer
Science MFCS, Lecture Notes in Computer Science 1893, 650-659.
- Sieling, D. (2000).
A separation of syntactic and nonsyntactic (1,+k)-branching
programs.
Computational Complexity 9, 247-263.
- Sieling, D. and Wegener, I. (2001).
A comparison of free BDDs and transformed BDDs.
Formal Methods in System Design 19, 223-236.
- Sieling, D. (2002).
The nonapproximability of OBDD minimization.
Information and Computation 172, 103-138.
- Sieling, D. (2002).
Lower bounds for linearly transformed OBDDs and FBDDs.
Journal of Computer and System Sciences 64, 419-438.
- Sieling, D. (2002).
The complexity of minimizing and learning OBDDs and FBDDs.
Discrete Applied Mathematics 122, 263-282.
- Sieling, D. (2003).
Minimization of decision trees is hard to approximate.
Proc. of 18th Computational Complexity Conference, 84-92.
- Sauerhoff, M. and Sieling, D. (2005).
Quantum branching programs and space-bounded nonuniform quantum
computation.
Theoretical Computer Science 334, 177-225.
- Savický, P. and Sieling, D. (2005).
A hierarchy result for read-once branching
programs with restricted parity nondeterminism.
Theoretical Computer Science 340, 594-605.
- Sieling, D. (2008).
Minimization of decision trees is hard to approximate.
Journal of Computer and System Sciences 74, 394-403.
- Sieling, D. (2009).
Minimization problems for parity OBDDs.
Theory of Computing Systems 44, 391-413.
Special Section Article
- Drechsler, R. and Sieling, D. (2001).
Binary decision diagrams in theory and practice.
Introductory article of a Special Section on BDDs, edited by Drechsler,
R. and Sieling, D.
Software Tools for Technology Transfer 3, 112-136.
The introductory article as well as the whole special section is
available
at http://link.springer.de/link/service/journals/10009/tocs/t1003002.htm
(external link, access to the full papers is restricted by Springer).
Further Publications
- Sieling, D. (1998).
Derandomization.
In: Lectures on Proof Verification and Approximation Algorithms, Mayr,
E.W., Prömel, H.J, Steger, A. (eds.), Lecture Notes in Computer
Science
1367, Springer, 41-61.
- Sieling, D. (2000).
Restricted branching programs with parity-type augmentations-lower
bounds and algorithms.
Abstract of an invited talk at ICALP-Workshop "Workshop on Boolean
Functions and Applications."
Proceedings of the Satellite Workshops of the 27th International
Colloquium
on Automata, Languages and Programming, Carleton Scientific, 259-262.
- Sieling, D. (2006).
Poker per E-Mail (in German).
Contribution to the series "Algorithmus der Woche" edited by Fakultätentag Informatik.
Available at http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo29.php.
- Bollig, B., Sauerhoff, M., Sieling, D. and Wegener, I. (2010).
Binary
decision diagrams.
Boolean Models and Methods in Mathematics, Computer Science and Engineering,
edited by Crama, Y. and Hammer, P.
Cambridge University Press, 473-505.
Theses
- Sieling, D. (1991).
Einwegfunktionen in der NC-Hierarchie (in German).
Diploma thesis, Universität Dortmund.
- Sieling, D. (1994).
Algorithmen und untere Schranken für verallgemeinerte OBDDs (in
German).
Ph.D. thesis, Universität Dortmund. Shaker, Aachen, 1995.
- Sieling, D. (2000).
On the Complexity of Manipulating and Representing Boolean Functions
by Restricted Branching Programs or Binary Decision Diagrams.
Habilitation thesis, Universität Dortmund.
Further Technical Reports
Lecture Notes
- Lecture "Theory of Logic Design" (in German), 2000.
(Postscript,
PDF)
- Lecture "Binary Decision Diagrams" (in German), 2003/2004.
(Postscript, PDF)
- Lecture "Online Algorithms" (in German), 2007.
(Postscript, PDF)
-
Lecture "Quantum algorithms and quantum cryptography", Part II on quantum cryptography (in German), 2007.
(Postscript, PDF)
Detlef
Sieling