Hermann Gruber

Proceedings of the SOFSEM 2025: Theory and Practice of Computer Science, 2025

2024

On Pumping Preserving Homomorphisms and the Complexity of the Pumping Problem (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2024

The Pumping Lemma for Context-Free Languages is Undecidable.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 28th International Conference, 2024

2023

The Pumping Lemma for Regular Languages is Hard.

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2023

2022

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

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2022

2021

Optimal Regular Expressions for Palindromes of Given Length.

[BibT_eX]

[DOI]

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

Enumerating regular expressions and their languages.

[BibT_eX]

[DOI]

Jonathan Lee

Jeffrey O. Shallit

Proceedings of the Handbook of Automata Theory., 2021

Descriptional complexity of regular languages.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Automata Theory., 2021

2020

On Minimizing Regular Expressions Without Kleene Star.

[BibT_eX]

[DOI]

Simon Wolfsteiner

Electron. Colloquium Comput. Complex., 2020

2018

On Minimal Grammar Problems for Finite Languages.

[BibT_eX]

[DOI]

Simon Wolfsteiner

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

2017

More on deterministic and nondeterministic finite cover automata.

[BibT_eX]

[DOI]

Sebastian Jakobi

Theor. Comput. Sci., 2017

2015

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

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2015

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

[BibT_eX]

[DOI]

Sebastian Jakobi

Proceedings of the Implementation and Application of Automata, 2015

2013

Provably Shorter Regular Expressions from Finite Automata.

[BibT_eX]

[DOI]

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

2012

Digraph Complexity Measures and Applications in Formal Language Theory.

[BibT_eX]

[DOI]

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

Enumerating regular expressions and their languages

[BibT_eX]

[DOI]

Jonathan Lee

Jeffrey O. Shallit

CoRR, 2012

2011

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

[BibT_eX]

[DOI]

Discret. Appl. Math., 2011

2010

On the descriptional and algorithmic complexity of regular languages.

[BibT_eX]

[DOI]

PhD thesis, 2010

On Balanced Separators, Treewidth, and Cycle Rank

[BibT_eX]

[DOI]

CoRR, 2010

Simplifying Regular Expressions.

[BibT_eX]

[DOI]

Stefan Gulan

Proceedings of the Language and Automata Theory and Applications, 2010

2009

Language operations with regular expressions of polynomial size.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

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

[BibT_eX]

[DOI]

Fundam. Informaticae, 2009

On Measuring Non-Recursive Trade-Offs

[BibT_eX]

[DOI]

Proceedings of the Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems, 2009

Short Regular Expressions from Finite Automata: Empirical Results.

[BibT_eX]

[DOI]

Michael Tautschnig

Proceedings of the Implementation and Application of Automata, 2009

Tight Bounds on the Descriptional Complexity of Regular Expressions.

[BibT_eX]

[DOI]

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

2008

Finite Automata, Digraph Connectivity, and Regular Expression Size.

[BibT_eX]

[DOI]

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

Optimal Lower Bounds on Regular Expression Size Using Communication Complexity.

[BibT_eX]

[DOI]

Jan Johannsen

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

Provably Shorter Regular Expressions from Deterministic Finite Automata.

[BibT_eX]

[DOI]

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

2007

The size of Higman-Haines sets.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

On the average state and transition complexity of finite languages.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

Computational Complexity of NFA Minimization for Finite and Unary Languages.

[BibT_eX]

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.

[BibT_eX]

[DOI]

Oliver Ruepp

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

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

[BibT_eX]

[DOI]

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

2006

Finding Lower Bounds for Nondeterministic State Complexity is Hard.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

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

[BibT_eX]