Christian Rauch 0001

dblp:51/7703-1 · DBLP profile ↗
← Back
11ranked-venue papers
0as first author
11since 2021 · last 2026
0000-0003-1008-4642ORCID · conflict

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 10 · 10 since 2021Applied, interdisciplinary, general and emerging computing · 2 · 2 since 2021
YearPublicationVenuePosition
2026 The Stanat-Weiss Pumping Lemma, Revisited (Extended Abstract)
Hermann Gruber, Markus Holzer 0001, Christian Rauch 0001
CIAA3
2026 On Jaffe's pumping lemma, revisited
abstract
We consider Jaffe's pumping lemma [ J. Jaffe . A necessary and sufficient pumping lemma for regular languages. SIGACT News , Summer, 1978] from a descriptional complexity perspective. Jaffe's pumping lemma is a necessary and sufficient condition for a language for being regular. Building on this, we improve on a result of [ A. Yehudai . A note on the pumping lemma for regular languages. Inform. Proc. Lett. , 9(3):135–136, 1979] by proving the existence of a regular language over an alphabet Σ with at least two symbols whose deterministic state complexity lies strictly between p , the minimal pumping constant in Jaffe's lemma, and ∑ i = 0 p − 1 | Σ | i . This finding aligns with recent work on minimal pumping constants for various pumping lemmas, as studied in [ J. Dassow and I. Jecker . Operational complexity and pumping lemmas. Acta Inform. , 59:337–355, 2022]. We further compare the minimal pumping constant in Jaffe's lemma with those of other well-known pumping lemmata from the literature, demonstrating that, in most cases, these constants can be independently assigned across the different lemmata.
Markus Holzer 0001, Christian Rauch 0001
Inf. Comput.2
2025 On Pumping Problems for Unary Regular Languages
Hermann Gruber, Markus Holzer 0001, Christian Rauch 0001
SOFSEM (2)3
2025 More on Language Families with a Decidable Pumping-Problem (Extended Abstract)
Markus Holzer 0001, Christian Rauch 0001
CIAA2
2024 The Pumping Lemma for Context-Free Languages is Undecidable
Hermann Gruber, Markus Holzer 0001, Christian Rauch 0001
DLT3
2024 On Pumping Preserving Homomorphisms and the Complexity of the Pumping Problem (Extended Abstract)
Hermann Gruber, Markus Holzer 0001, Christian Rauch 0001
CIAA3
2023 Computational Complexity of Reversible Reaction Systems
Markus Holzer 0001, Christian Rauch 0001
RC2
2023 The Pumping Lemma for Regular Languages is Hard
Hermann Gruber, Markus Holzer 0001, Christian Rauch 0001
CIAA3
2022 On 25 Years of CIAA Through the Lens of Data Science
Hermann Gruber, Markus Holzer 0001, Christian Rauch 0001
CIAA3
2021 The Range of State Complexities of Languages Resulting from the Cascade Product - The General Case (Extended Abstract)
Markus Holzer 0001, Christian Rauch 0001
DLT2
2021 The Range of State Complexities of Languages Resulting from the Cascade Product - The Unary Case (Extended Abstract)
Markus Holzer 0001, Christian Rauch 0001
CIAA2