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

• Bollig, B., Sauerhoff, M., Sieling, D. and Wegener, I. (1993).
  Read-k-times ordered binary decision diagrams - efficient algorithms in the presence of null-chains.
  Tech. Report No. 474, Universität Dortmund.
   
• Sieling, D. (1994).
  On the complexity of operations on graph driven BDDs and tree driven BDDs.
  Tech. Report No. 554, Universität Dortmund.
   

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