| 2008 | CiE | Complexity of Aperiodicity for Topological Properties of Regular omega-Languages. | Victor L. Selivanov, Klaus W. Wagner |
| 2008 | DLT | Complexity of Topological Properties of Regular omega-Languages. | Victor L. Selivanov, Klaus W. Wagner |
| 2007 | STACS | The Complexity of Unions of Disjoint Sets. | Christian Glaer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner |
| 2006 | DLT | Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy. | Christian Glaer, Stephen D. Travers, Klaus W. Wagner |
| 2004 | MCU | Leaf Language Classes. | Klaus W. Wagner |
| 2004 | MFCS | Generation Problems. | Elmar Bhler, Christian Glaer, Bernhard Schwarz, Klaus W. Wagner |
| 2004 | MFCS | A Reducibility for the Dot-Depth Hierarchy. | Victor L. Selivanov, Klaus W. Wagner |
| 2003 | FCT | On the Exponentiation of Languages. | Werner Kuich, Klaus W. Wagner |
| 2003 | STACS | The Complexity of Membership Problems for Circuits over Sets of Natural Numbers. | Pierre McKenzie, Klaus W. Wagner |
| 2001 | ICALP | The Complexity of Computing the Size of an Interval. | Lane A. Hemaspaandra, Sven Kosub, Klaus W. Wagner |
| 2000 | STACS | The Boolean Hierarchy of NP-Partitions. | Sven Kosub, Klaus W. Wagner |
| 1998 | COCOON | On Boolean Lowness and Boolean Highness. | Steffen Reith, Klaus W. Wagner |
| 1996 | ICALP | On Type-2 Probabilistic Quantifiers. | Ronald V. Book, Heribert Vollmer, Klaus W. Wagner |
| 1993 | STACS | The Alternation Hierarchy for Sublogarithmic Space: An Exciting Race to STACS'93 (Editorial Note). | Klaus W. Wagner |
| 1992 | STACS | On Complexity Classes and Algorithmically Random Languages (Extended Abstract). | Ronald V. Book, Jack H. Lutz, Klaus W. Wagner |
| 1990 | CSL | Interactive Proof Systems: Provers, Rounds, and Error Bounds. | Ulrich Hertrampf, Klaus W. Wagner |
| 1990 | MFCS | Vector Language: Simple Description of Hard Instances (Extended Abstract). | Miroslaw Kowaluk, Klaus W. Wagner |
| 1988 | ICALP | On Restricting the Access to an NP-Oracle. | Klaus W. Wagner |
| 1988 | STACS | Collapsing Oracle Hierarchies, Census Functions and Logarithmically Many Queries. | Uwe Schning, Klaus W. Wagner |
| 1987 | STACS | The Correlation Between the Complexities of the Nonhierarchical and Hierarchical Versions of Graph Problems. | Thomas Lengauer, Klaus W. Wagner |
| 1986 | ICALP | More Complicated Questions About Maxima and Minima, and Some Closures of NP. | Klaus W. Wagner |
| 1983 | FCT | Reversal-Bounded and Visit-Bounded Realtime Computations. | Andreas Brandstdt, Klaus W. Wagner |
| 1979 | MFCS | Bounded Recursion and Complexity Classes. | Klaus W. Wagner |
| 1977 | FCT | Recursive omega-Languages. | Klaus W. Wagner, Ludwig Staiger |
| 1977 | MFCS | Complexity Hierarchies of Oracles. | Klaus W. Wagner, Gerd Wechsung |
| 1975 | MFCS | A Hierarchy of Regular Sequence Sets. | Klaus W. Wagner |
| 1974 | MFCS | Finite Automata Acceptation of Infinite Sequences. | Klaus W. Wagner, Ludwig Staiger |