Technical Reports of the Department for Theoretical Computer Science and new Applications
Research Activities
This is a List of Technical Reports published by us in the Years 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002 2003 Click on the Number for an ASCII Abstract, and on the Title for the full PostScript Version. We have online Versions of our biannual Reports, too - available for 1992/93, 1994/95, 1996/97,1998/99, 2000 2001, 2002
2003
- 3
- Zhou / Meinel
-
- Implement Role-Based Access Control with Attribute Certificates
2002
- 21
- Schillings / Meinel
- tele-TASK - Teleteaching Anywhere Solution Kit
- 20
- Bryant / Meinel
- Ordered Binary Decision Diagrams in Electronic Design Automation
2001
- 21
- Meinel / Sack / Schillings
- VisBDD - A Webbased Visualization Framework for OBDD Algorithms
- 16
- Meinel / Stangier
- Modular Partitioning for Improvement of Image Computation
- 15
- Meinel / Sack / Schillings
- IDDS: An Interactive Decentralized Documentation System
- 09
- Meinel / Sack
- WWW.BDD-PORTAL.ORG: An Experimentation Platform For BDD Algorithms
- 07
- Meinel / Sack
- Improving XOR-Node Placement for (+)-OBDDs
- 06
- Meinel / Sack
- A Heuristic for (+)-OBDD Minimization
- 05
- M. Mundhenk:
- 43. Workshop für Komplexitätstheorie, Datenstrukturen und effiziente Algorithmen (Theorietag)
- 04
- Meinel / Mundhenk:
- 6. Berlin-München-Trierer Workshop zur Algorithmischen Diskreten Mathematik und Mathematischen Optimierung (ADiMMO 2001)
2000
- 00-13
- R. Mubarakzjanov:
-
-
- Lower Bounds for Randomized Branching Programs with a Big OBDD Part
- 00-12
- Ch. Lusena, J. Goldsmith, M.Mundhenk:
-
-
- Nonapproximability Results for Partially Observable Markov Decision Processes
1999
- 99-29
- Chr. Stangier, U. Holtmann:
- Applying Formal Verification with Protocol Compiler
- 99-28
- Ch. Meinel, Chr. Stangier:
- Speeding Up Symbolic Model Checking by Accelerating Dynamic Variable Reordering
- 99-27
- H. Sack, E. Dubrova, Ch. Meinel:
- Mod-p Decision Diagrams: A Data Structure for Multiple-Valued Functions
- 99-26
- G. Hoff, M. Mundhenk:
- Finding Scientific Papers with HPSearch and MOPS
- 99-25
- M. Mundhenk, J. Goldsmith, C. Lusena, E. Allender:
- Complexity of Finite-Horizon Markov Decision Process Problems
- 99-23
- E. Dubrova, H. Sack:
- Probabilistic Verification of Multiple-Valued Functions
- 99-22
- M. Mundhenk:
- The Complexity of Optimal Small Policies
- 99-21
- M. Mundhenk:
- Propositional Proofs and Their Complexity [DVI file with hyperlinks]
- 99-20
- C. Damm:
- On the Complexity of Tensor Formulae
- 99-19
- Ch. Meinel, H. Sack:
- Algorithmic Considerations for
-OBDD Reordering - 99-16
- J. Bern, Ch. Meinel:
- One Step Further: Integrating Electronic Submission and the Reviewing Process
1998
- 98-29
- Ch. Meinel, H. Sack, Chr. Stangier, A. Wagner:
- Do We Really Need Common Variable Orders for Synthesizing OBDDs?
- 98-28
- Ch. Meinel, H. Sack:
- -OBDDs - a BDD Structure for Probabilistic Verification
- 98-27
- Ch. Meinel, A. Wagner:
- The WWW meets EDA: Usability evaluation of OBDD-heuristics via the Internet
- 98-25
- Ch. Meinel, A. Slobodová:
- Accelerating OBDD-Minimization by Means of Structural and Semantical Properties
- 98-24
- Ch. Meinel, K. Schwettmann, A. Slobodová:
- Application Driven Variable Reordering and an Example in Reachability Analysis
- 98-23
- Ch. Meinel, Chr. Stangier:
- Increasing Efficiency of Symbolic Model Checking by Accelerating Dynamic Variable Reordering
- 98-22
- G. Cabodi, S. Quer, Ch. Meinel, H. Sack, A. Slobodová, Chr. Stangier:
- Binary Decision Diagrams and the Multiple Variable Order Problem
- 98-21
- A. Bernasconi, C. Damm, I. Shparlinski:
- Circuit and Decision Tree Complexity of Some Number Theoretic Problems
- 98-20
- C. Damm:
- On Alternating vs. Parity Communication Complexity
- 98-06
- C. Damm:
- On Boolean vs. Modular Arithmetic for Circuits and Communication Protocols
- 98-01
- Ch. Meinel, Th. Theobald:
- Ordered Binary Decision Diagrams and Their Significance in Computer-Aided Design of VLSI Circuits
1997
- 97-28
- Ch. Meinel, C. Stangier:
- OBDD-based Verification of Communication Protocols - Methods for the Verification of Data Link Protocols
- 97-27
- Ch. Meinel, A. Slobodová, P. Willems:
- Block-Restricted Reordering - Extended Experiments -
- 97-21
- C. Damm:
- A Note on Spectral Lower Bound Arguments for Decision Trees
- 97-19
- Ch. Meinel, C. Damm, M. Mundhenk (ed.):
- 33. Workshop über Komplexitätstheorie, Datenstrukturen und effiziente Algorithmen
- 97-16
- J. Bern, C. Damm, Ch. Meinel:
- The Electronic Colloquium on Computational Complexity (ECCC): A Digital Library in Use
- (See this remark on the figures in the appendix, too)
- 97-15
- Ch. Meinel, H. Sack:
- Case Study: Manipulating -OBDDs by Means of Signatures
- 97-14
- Ch. Meinel, F. Somenzi, Th. Theobald:
- Function Decomposition and Synthesis Using Linear Sifting
1996
- 96-42
- Ch. Meinel, F. Somenzi, Th. Theobald:
- Linear Sifting of Decision Diagrams
- 96-40
- Ch. Meinel, A. Slobodová:
- Speeding up Variable Reordering of OBDDs
- 96-26
- A. Czumaj, P. Kanarek, M. Kutylowski, K. Lorys:
- Fast Generation of Random Permutations via Networks Simulation
- 96-23
- Ch. Meinel, Th. Theobald:
- Local Encoding Transformations for Optimizing OBDD-Representations of Finite State Machines
Presented on FMCAD'96, Palo Alto (California, USA); Lecture Notes in Computer Science No. 1166, pp. 404-418, Springer Verlag, 1996 - 96-07
- U. Hertrampf:
- On the Acceptance Power of Groups and Semigroups
- 96-04
- T. Theobald, Ch. Meinel:
- State Encodings and OBDD-Sizes
- 96-02
- Ch. Meinel, A. Slobodová:
- An Adequate Reducibility Concept for Problems Defined in Terms of Ordered Binary Decision Diagrams
To appear in Mathematical Systems Theory, Springer International
1995
- 95-21
- Ch. Meinel:
- Die Entwicklung der Informatik braucht Theorie und Praxis. Ein Fallbeispiel aus dem CAD-Schaltkreisentwurf
Appeared in GISI'95 Herausforderungen eines globalen Informationsverbundes für die Informatik, F. Huber-Wäschle, H. Schauer, P. Widmayer ed., Informatik aktuell, pp. 339-346, Springer Verlag, 1995 - 95-17
- C. Damm, S. Jukna, J. Sgall:
- Some Bounds on Multiparty Communication Complexity of Pointer Jumping
Appeared in the ECCC Report Series as TR 95-044, 1995; see there. - 95-11
- S. Jukna:
- On Communication Games with More than Two Players
- 95-10
- S. Jukna:
- The Graph of Integer Multiplication is Hard for Read-k-Times Networks
- 95-09
- C. Damm, S. Jukna:
- On Multiparity Games for Pointer Jumping
- 95-03
- J. Bern, Ch. Meinel, A. Slobodová:
- Global Rebuilding of OBDD's - Tunnelling Memory Requirement Maxima
- 95-02
- M. Mundhenk:
- Monotonous Oracle Machines
Presented on the 2nd Latin-American Conference on Theoretical Informatics; Lecture Notes in Computer Science No. 911, pp. 436-448, Springer Verlag, 1995 - 95-01
- C. Damm, M. Holzer, P. Rossmanith:
- Expressing Uniformity via Oracles
Presented at the 7th International Meeting of Young Computer Scientists, 1992
Appeared in "Developments in Theoretical Computer Science", pp. 83-92, Gordon and Beach Science Publishers, Switzerland, 1994
1994
- 94-17
- Ch. Meinel, A. Slobodová:
- A Unifying Theoretical Background for Some BDD-based Data Structures
To appear in Formal Methods in System Design, Kluwer Academic Publishers - 94-16
- J. Bern, Ch. Meinel, A. Slobodová:
- Efficient OBDD-Based Boolean Manipulation in CAD Beyond Current Limits
Presented on the IEEE Design Automation Conference, San Francisco, June 12-16th, 1995 - 94-12
- C. Damm, M. Holzer:
- Inductive Counting below LOGSPACE
Presented on the Conference on Mathematical Foundations of Computer Science, Kosice, 1994; Lecture Notes in Computer Science No. 841, pp. 276-285, Springer Verlag - 94-06
- S. Jukna:
- Finite Limits and Lower Bounds for Circuits Size
- 94-05
- Ch. Meinel, A. Slobodová:
- On the Complexity of Constructing Optimal OBDD's
Presented on the Conference on Mathematical Foundations of Computer Science, Kosice, 1994; Lecture Notes in Computer Science No. 841, pp. 515-524, Springer Verlag - 94-04
- Ch. Meinel, St. Waack:
- The Möbius Function, Variations Ranks, and Theta(n)-Bounds on the Modular Communication Complexity of the Undirected Graph Connectivity Problem
- 94-03
- J. Bern, Ch. Meinel, A. Slobodová:
- Some Heuristics for Generating Tree-like FBDD Types
Appeared in IEEE Transactions on CAD, vol. 15, No. 1, pp. 127-130, 1996
1993
- 93-21
- J. Gergov, Ch. Meinel:
- Mod-2-OBDD's; A Generalization of OBDD's and EXOR-Sum-of-Products
Presented at the IFIP Workshop on Application of the Reed-Muller Expansion in Circuit Design, Hamburg, 1993 - 93-20
- J. Bern, J. Gergov, Ch. Meinel, A. Slobodová:
- Boolean Manipulation with Free BDD's - First Experimental Results
Presented on the European Design Automation Conference 1994; Proceedings available from IEEE Computer Society Press; pp. 200-207 - 93-16
- U. Hertrampf:
- Complexity Classes with Finite Acceptance Types
- 93-12
- J. Gergov, Ch. Meinel:
- Efficient Boolean Manipulation with OBDD's can be Extended to FBDD's
Appeared in IEEE Transactions on Computers, Vol. 43, No. 10 (1994), pp. 1197-1209, as "Efficient Analysis and Boolean Manipulation of OBDD's can be extended to FBDD's" - 93-09
- A. Slobodová, Ch. Meinel:
- Efficient Manipulation of FBDDs by Means of a Modified OBDD-Package
- 93-08
- J. Gergov, Ch. Meinel:
- Combinational Logic Verification with FBDDs
Presented on the 13th IFIP World Computer Congress '94 in Hamburg as "Boolean Manipulation with Free BDDs. An Application in Combinational Logic Verification" - 93-07
- C. Damm:
- How Much ExOR Improves on OR?
Presented on the IFIP WG 10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design, Hamburg, 1993; Proceedings available as Vol. WSI-93-2 of the "Berichte des Wilhelm-Schickard-Instituts für Informatik" Series, U. Kebschull / E. Schubert / W. Rosenstiel Ed., from the Wilhelm-Schickard-Instituts für Informatik, University of Tübingen; pp. 6-12 - 93-05
- C. Damm, K. Lenz:
- Symmetric Functions in AC^0[2]
1992
- 92-28
- U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer, K. W. Wagner:
- On the Power of Polynomial Bit-Reductions
- 92-17
- Program of the 18th Workshop on Complexity Theory, Efficient Algorithms and Data Structures
- (which took place at Trier on 20-Oct-1992)
- 92-10
- J. Gergov, Ch. Meinel:
- Efficient Analysis and Manipulation of OBDDs can be Extended to Read-once-only Branching Programs
(Please see the updated Version instead: 93-12: Gergov, Meinel: Efficient Boolean Manipulation with OBDD's can be Extended to FBDD's) - 92-07
- J. Gergov, Ch. Meinel:
- Analysis and Manipulation of Boolean Functions in Terms of Decision Graphs
Presented on WG '92 in Frankfurt (Main) - 92-05
- Ch. Meinel:
- A Note on Möbius Functions and the Communication Complexity of the Graph-Accessability-Problem
- 92-04
- Ch. Meinel, S. Waack:
- Upper and Lower Bounds for Certain Graph-Accessability-Problems on Bounded Alternating (omega)-Branching Programs
Presented at MFCS'91, Kazimierz Dolny (Poland); Lecture Notes in Computer Science No. 520, pp. 337-345, Springer Verlag, 1991 - 92-01
- C. Damm, M. Krause, Ch. Meinel, S. Waack:
- Separating Counting Communication Complexity Classes
Presented on the 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, 1992; Lecture Notes in Computer Science No. 577, pp. 281-292, Finkel / Alain / Jantzen Ed., Springer Verlag
![[CS HOME]](http://www.informatik.uni-trier.de/icons/Home_Info.gif)
![[DPT. HOME]](http://www.informatik.uni-trier.de/icons/Home_TI.gif)
TCS+NA Research Page - webmaster - 22-Aug-2001