Hermann Gruber

46 papers B 3C 15Misc 1Journal 17Unranked 7
YearRankTypeTitle / Venue / Authors
2026 J jnl
The Pumping Lemma for Regular Languages is Hard.
Int. J. Found. Comput. Sci.
Hermann Gruber, Markus Holzer, Christian Rauch
2025 — conf
On Pumping Constants and Smallest Grammars for Context-Free Languages.
Languages of Cooperation and Communication
Hermann Gruber, Markus Holzer
2025 — conf
On Pumping Problems for Unary Regular Languages.
SOFSEM (2)
Hermann Gruber, Markus Holzer, Christian Rauch
2024 C conf
On Pumping Preserving Homomorphisms and the Complexity of the Pumping Problem (Extended Abstract).
CIAA
Hermann Gruber, Markus Holzer, Christian Rauch
2024 C conf
The Pumping Lemma for Context-Free Languages is Undecidable.
DLT
Hermann Gruber, Markus Holzer, Christian Rauch
2023 C conf
The Pumping Lemma for Regular Languages is Hard.
CIAA
Hermann Gruber, Markus Holzer, Christian Rauch
2022 C conf
On 25 Years of CIAA Through the Lens of Data Science.
CIAA
Hermann Gruber, Markus Holzer, Christian Rauch
2021 — ch.
Descriptional complexity of regular languages.
Handbook of Automata Theory (I.)
Hermann Gruber, Markus Holzer, Martin Kutrib
2021 — ch.
Enumerating regular expressions and their languages.
Handbook of Automata Theory (I.)
Hermann Gruber, Jonathan Lee, Jeffrey O. Shallit
2021 B conf
On Minimizing Regular Expressions Without Kleene Star.
FCT
Hermann Gruber, Markus Holzer, Simon Wolfsteiner
2021 B conf
Optimal Regular Expressions for Palindromes of Given Length.
MFCS
Hermann Gruber, Markus Holzer
2020 J jnl
On Minimizing Regular Expressions Without Kleene Star.
Electron. Colloquium Comput. Complex.
Hermann Gruber, Markus Holzer, Simon Wolfsteiner
2018 C conf
On Minimal Grammar Problems for Finite Languages.
DLT
Hermann Gruber, Markus Holzer, Simon Wolfsteiner
2017 J jnl
More on deterministic and nondeterministic finite cover automata.
Theor. Comput. Sci.
Hermann Gruber, Markus Holzer, Sebastian Jakobi
2015 J jnl
From Finite Automata to Regular Expressions and Back - A Summary on Descriptional Complexity.
Int. J. Found. Comput. Sci.
Hermann Gruber, Markus Holzer
2015 C conf
More on Deterministic and Nondeterministic Finite Cover Automata - Extended Abstract.
CIAA
Hermann Gruber, Markus Holzer, Sebastian Jakobi
2014 — conf
From Finite Automata to Regular Expressions and Back-A Summary on Descriptional Complexity.
AFL
Hermann Gruber, Markus Holzer
2013 J jnl
Provably Shorter Regular Expressions from Finite Automata.
Int. J. Found. Comput. Sci.
Hermann Gruber, Markus Holzer
2012 J jnl
Digraph Complexity Measures and Applications in Formal Language Theory.
Discret. Math. Theor. Comput. Sci.
Hermann Gruber
2012 J jnl
Enumerating regular expressions and their languages
CoRR
Hermann Gruber, Jonathan Lee, Jeffrey O. Shallit
2011 J jnl
Bounding the Feedback Vertex Number of Digraphs in Terms of Vertex Degrees
CoRR
Hermann Gruber
2011 J jnl
Bounding the feedback vertex number of digraphs in terms of vertex degrees.
Discret. Appl. Math.
Hermann Gruber
2011 J jnl
Digraph Complexity Measures and Applications in Formal Language Theory
CoRR
Hermann Gruber
2010 J jnl
On Balanced Separators, Treewidth, and Cycle Rank
CoRR
Hermann Gruber
2010 J jnl
On Measuring Non-recursive Trade-Offs.
J. Autom. Lang. Comb.
Hermann Gruber, Markus Holzer, Martin Kutrib
2010 — —
On the descriptional and algorithmic complexity of regular languages.
Hermann Gruber
2010 C conf
Simplifying Regular Expressions.
LATA
Hermann Gruber, Stefan Gulan
2009 J jnl
Language operations with regular expressions of polynomial size.
Theor. Comput. Sci.
Hermann Gruber, Markus Holzer
2009 J jnl
More on the Size of Higman-Haines Sets: Effective Constructions.
Fundam. Informaticae
Hermann Gruber, Markus Holzer, Martin Kutrib
2009 — conf
On Measuring Non-Recursive Trade-Offs
DCFS
Hermann Gruber, Markus Holzer, Martin Kutrib
2009 C conf
Short Regular Expressions from Finite Automata: Empirical Results.
CIAA
Hermann Gruber, Markus Holzer, Michael Tautschnig
2009 C conf
Tight Bounds on the Descriptional Complexity of Regular Expressions.
Developments in Language Theory
Hermann Gruber, Markus Holzer
2008 — conf
Finite Automata, Digraph Connectivity, and Regular Expression Size.
ICALP (2)
Hermann Gruber, Markus Holzer
2008 — conf
Language Operations with Regular Expressions of Polynomial Size.
DCFS
Hermann Gruber, Markus Holzer
2008 B conf
Optimal Lower Bounds on Regular Expression Size Using Communication Complexity.
FoSSaCS
Hermann Gruber, Jan Johannsen
2008 C conf
Provably Shorter Regular Expressions from Deterministic Finite Automata.
Developments in Language Theory
Hermann Gruber, Markus Holzer
2007 C conf
Computational Complexity of NFA Minimization for Finite and Unary Languages.
LATA
Hermann Gruber, Markus Holzer
2007 C conf
Inapproximability of Nondeterministic State and Transition Complexity Assuming P=!NP.
Developments in Language Theory
Hermann Gruber, Markus Holzer
2007 C conf
More on the Size of Higman-Haines Sets: Effective Constructions.
MCU
Hermann Gruber, Markus Holzer, Martin Kutrib
2007 J jnl
On the average state and transition complexity of finite languages.
Theor. Comput. Sci.
Hermann Gruber, Markus Holzer
2007 Misc conf
Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms.
FUN
Hermann Gruber, Markus Holzer, Oliver Ruepp
2007 J jnl
The size of Higman-Haines sets.
Theor. Comput. Sci.
Hermann Gruber, Markus Holzer, Martin Kutrib
2006 C conf
Finding Lower Bounds for Nondeterministic State Complexity Is Hard.
Developments in Language Theory
Hermann Gruber, Markus Holzer
2006 J jnl
Finding Lower Bounds for Nondeterministic State Complexity is Hard.
Electron. Colloquium Comput. Complex.
Hermann Gruber, Markus Holzer
2006 — conf
Results on the Average State and Transition Complexity of Finite Automata Accepting Finite Languages (Extended Abstract).
DCFS
Hermann Gruber, Markus Holzer
2005 C conf
On Timed Automata with Discrete Time - Structural and Language Theoretical Characterization.
Developments in Language Theory
Hermann Gruber, Markus Holzer, Astrid Kiehn, Barbara König