| 2019 | COCOON | LIKE Patterns and Complexity. | Holger Petersen |
| 2017 | FCT | Busy Beaver Scores and Alphabet Size. | Holger Petersen |
| 2016 | SODA | Simpler, faster and shorter labels for distances in graphs. | Stephen Alstrup, Cyril Gavoille, Esben Bistrup Halvorsen, Holger Petersen |
| 2014 | GI | Professionelles Testmanagement in Datenreinigungsprozessen. | Holger Petersen |
| 2009 | DLT | Simulations by Time-Bounded Counter Machines. | Holger Petersen |
| 2008 | LATA | Sorting and Element Distinctness on One-Way Turing Machines. | Holger Petersen |
| 2008 | SOFSEM | Element Distinctness and Sorting on One-Tape Off-Line Turing Machines. | Holger Petersen |
| 2008 | SOFSEM | Improved Bounds for Range Mode and Range Median Queries. | Holger Petersen |
| 2002 | STACS | The Membership Problem for Regular Expressions with Intersection Is Complete in LOGCFL. | Holger Petersen |
| 2001 | COCOON | Stacks versus Deques. | Holger Petersen |
| 2000 | MFCS | Separation Results for Rebound Automata. | Holger Petersen |
| 1999 | MFCS | Fooling Rebound Automata. | Holger Petersen |
| 1999 | STOC | Backing Up in Singly Linked Lists. | Amir M. Ben-Amram, Holger Petersen |
| 1998 | ICALP | CONS-Free Programs with Tree Input (Extended Abstract). | Amir M. Ben-Amram, Holger Petersen |
| 1998 | ICALP | Efficient Simulations by Queue Machines. | Holger Petersen, John Michael Robson |
| 1998 | MFCS | The Head Hierarchy for Oblivious Finite Automata with Polynomial Advice Collapses. | Holger Petersen |
| 1997 | FCT | The Equivalence of Pebbles and Sensing Heads for Finite Automata. | Holger Petersen |
| 1997 | MFCS | Homomorphic Images os Sentential Forms and Terminating Grammars (Extended Abstract). | Holger Petersen |
| 1996 | CCS | Breaking and Repairing a Convertible Undeniable Signature Scheme. | Markus Michels, Holger Petersen, Patrick Horster |
| 1995 | FCT | Some Results Concerning Two-Dimensional Turing Machines and Finite Automata. | Holger Petersen |
| 1995 | ICALP | Alternation in Simple Devices. | Holger Petersen |
| 1994 | ASIACRYPT | Meta-Message Recovery and Meta-Blind Signature Schemes Based on the Discrete Logarithm Problem and Their Applications. | Patrick Horster, Markus Michels, Holger Petersen |
| 1994 | CCS | Meta-ElGamal Signature Schemes. | Patrick Horster, Holger Petersen, Markus Michels |
| 1994 | STACS | The Ambiguity of Primitive Words. | Holger Petersen |
| 1993 | STACS | Cancellation on Context-Free Languages: Enrichment by Reduction. | Matthias Jantzen, Holger Petersen |
| 1987 | FCT | Dyck | Matthias Jantzen, Manfred Kudlek, Klaus-Jrn Lange, Holger Petersen |