Hermann Gruber

According to our database, Hermann Gruber authored at least 33 papers between 2005 and 2023.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2023

The Pumping Lemma for Regular Languages is Hard.

Hermann Gruber, Markus Holzer, Christian Rauch

Proceedings of the Implementation and Application of Automata, 2023

2022

On 25 Years of CIAA Through the Lens of Data Science.

Hermann Gruber, Markus Holzer, Christian Rauch

Proceedings of the Implementation and Application of Automata, 2022

2021

Optimal Regular Expressions for Palindromes of Given Length.

Hermann Gruber, Markus Holzer

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

Enumerating regular expressions and their languages.

Hermann Gruber, Jonathan Lee, Jeffrey O. Shallit

Proceedings of the Handbook of Automata Theory., 2021

Descriptional complexity of regular languages.

Hermann Gruber, Markus Holzer, Martin Kutrib

Proceedings of the Handbook of Automata Theory., 2021

2020

On Minimizing Regular Expressions Without Kleene Star.

Hermann Gruber, Markus Holzer, Simon Wolfsteiner

Electron. Colloquium Comput. Complex., 2020

2018

On Minimal Grammar Problems for Finite Languages.

Hermann Gruber, Markus Holzer, Simon Wolfsteiner

Proceedings of the Developments in Language Theory - 22nd International Conference, 2018

2017

More on deterministic and nondeterministic finite cover automata.

Hermann Gruber, Markus Holzer, Sebastian Jakobi

Theor. Comput. Sci., 2017

2015

More on Deterministic and Nondeterministic Finite Cover Automata - Extended Abstract.

Hermann Gruber, Markus Holzer, Sebastian Jakobi

Proceedings of the Implementation and Application of Automata, 2015

2014

From Finite Automata to Regular Expressions and Back-A Summary on Descriptional Complexity.

Hermann Gruber, Markus Holzer

Proceedings of the Proceedings 14th International Conference on Automata and Formal Languages, 2014

2013

Provably Shorter Regular Expressions from Finite Automata.

Hermann Gruber, Markus Holzer

Int. J. Found. Comput. Sci., 2013

2012

Digraph Complexity Measures and Applications in Formal Language Theory.

Hermann Gruber

Discret. Math. Theor. Comput. Sci., 2012

Enumerating regular expressions and their languages

Hermann Gruber, Jonathan Lee, Jeffrey O. Shallit

CoRR, 2012

2011

Bounding the feedback vertex number of digraphs in terms of vertex degrees.

Hermann Gruber

Discret. Appl. Math., 2011

2010

On the descriptional and algorithmic complexity of regular languages.

Hermann Gruber

PhD thesis, 2010

On Measuring Non-recursive Trade-Offs.

Hermann Gruber, Markus Holzer, Martin Kutrib

J. Autom. Lang. Comb., 2010

On Balanced Separators, Treewidth, and Cycle Rank

Hermann Gruber

CoRR, 2010

Simplifying Regular Expressions.

Hermann Gruber, Stefan Gulan

Proceedings of the Language and Automata Theory and Applications, 2010

2009

Language operations with regular expressions of polynomial size.

Hermann Gruber, Markus Holzer

Theor. Comput. Sci., 2009

More on the Size of Higman-Haines Sets: Effective Constructions.

Hermann Gruber, Markus Holzer, Martin Kutrib

Fundam. Informaticae, 2009

Short Regular Expressions from Finite Automata: Empirical Results.

Hermann Gruber, Markus Holzer, Michael Tautschnig

Proceedings of the Implementation and Application of Automata, 2009

Tight Bounds on the Descriptional Complexity of Regular Expressions.

Hermann Gruber, Markus Holzer

Proceedings of the Developments in Language Theory, 13th International Conference, 2009

2008

Finite Automata, Digraph Connectivity, and Regular Expression Size.

Hermann Gruber, Markus Holzer

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Optimal Lower Bounds on Regular Expression Size Using Communication Complexity.

Hermann Gruber, Jan Johannsen

Proceedings of the Foundations of Software Science and Computational Structures, 2008

Provably Shorter Regular Expressions from Deterministic Finite Automata.

Hermann Gruber, Markus Holzer

Proceedings of the Developments in Language Theory, 12th International Conference, 2008

2007

The size of Higman-Haines sets.

Hermann Gruber, Markus Holzer, Martin Kutrib

Theor. Comput. Sci., 2007

On the average state and transition complexity of finite languages.

Hermann Gruber, Markus Holzer

Theor. Comput. Sci., 2007

Computational Complexity of NFA Minimization for Finite and Unary Languages.

Hermann Gruber, Markus Holzer

Proceedings of the LATA 2007. Proceedings of the 1st International Conference on Language and Automata Theory and Applications., 2007

Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms.

Hermann Gruber, Markus Holzer, Oliver Ruepp

Proceedings of the Fun with Algorithms, 4th International Conference, 2007

Inapproximability of Nondeterministic State and Transition Complexity Assuming P=!NP.

Hermann Gruber, Markus Holzer

Proceedings of the Developments in Language Theory, 11th International Conference, 2007

2006

Finding Lower Bounds for Nondeterministic State Complexity is Hard.

Hermann Gruber, Markus Holzer

Electron. Colloquium Comput. Complex., 2006

Results on the Average State and Transition Complexity of Finite Automata Accepting Finite Languages (Extended Abstract).

Hermann Gruber, Markus Holzer

Proceedings of the 8th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2006, Las Cruces, New Mexico, USA, June 21, 2006

2005

On Timed Automata with Discrete Time - Structural and Language Theoretical Characterization.

Hermann Gruber, Markus Holzer, Astrid Kiehn, Barbara König

Proceedings of the Developments in Language Theory, 9th International Conference, 2005