Copyright Notice: All material on this page is copyright by the authors or other copyright holders. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and bear the full citation and a possible copyright notice on the first page. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. In particular, work published in the Springer LNCS Series is © Springer-Verlag.
| • |
Hermann Gruber, Markus Holzer, and Christian Rauch.
On Pumping Preserving Homomorphisms and the Complexity of the
Pumping Problem (Extended Abstract).
In Szilárd Zsolt Fazekas, editor, 28th International
Conference on Implementation and Application of Automata (CIAA 2024), Akita,
Japan, Lecture Notes in Computer Science. Springer, 2024.
PDF venue |
| • |
Hermann Gruber, Markus Holzer, and Christian Rauch.
The Pumping Lemma for Context-Free Languages is Undecidable.
In Florin Manea, editor, 28th International Conference on
Developments in Language Theory (DLT 2024), Göttingen, Germany, Lecture
Notes in Computer Science. Springer, 2024.
PDF venue |
| • |
Hermann Gruber, Markus Holzer, and Christian Rauch.
The Pumping Lemma for Regular Languages is Hard.
In Benedek Nagy, editor, 27th International Conference on
Implementation and Application of Automata (CIAA 2023), Famagusta,
Türkiye, volume 14151 of Lecture Notes in Computer Science, pages
128--140. Springer, September 2023.
PDF venue official |
| • |
Hermann Gruber, Markus Holzer, and Christian Rauch.
On 25 Years of CIAA Through the Lens of Data Science.
In Pascal Caron and Ludovic Mignot, editors, 26th International
Conference on Implementation and Application of Automata (CIAA 2022), Rouen,
France, volume 13266 of Lecture Notes in Computer Science, pages
3--18. Springer, June 2022.
PDF venue official |
| • |
Hermann Gruber and Markus Holzer.
Optimal Regular Expressions for Palindromes of Given Length.
In Filippo Bonchi and Simon J. Puglisi, editors, 46th
International Symposium on Mathematical Foundations of Computer Science (MFCS
2021), Tallinn, Estonia, Leibniz International Proceedings in Informatics,
pages 52:1--52:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
September 2021.
PDF venue official |
| • |
Hermann Gruber, Markus Holzer, and Simon Wolfsteiner.
On Minimizing Regular Expressions Without Kleene Star.
In Evripidis Bampis and Aris Pagourtzis, editors, 23rd
International Symposium on Fundamentals of Computation Theory (FCT 2021),
Athens, Greece, volume 12867 of Lecture Notes in Computer Science,
pages 245--258. Springer, September 2021.
PDF venue official |
| • |
Hermann Gruber, Markus Holzer, and Simon Wolfsteiner.
On Minimal Grammar Problems for Finite Languages.
In Mizuho Hoshi and Shinnosuke Seki, editors, 22nd International
Conference on Developments in Language Theory (DLT 2018), Tokyo, Japan,
volume 11088 of Lecture Notes in Computer Science, pages 342--353.
Springer, September 2018.
PDF venue official |
| • |
Hermann Gruber, Markus Holzer, and Sebastian Jakobi.
More on Deterministic and Nondeterministic Finite Cover Automata
(Extended Abstract).
In Frank Drewes, editor, 20th International Conference on
Implementation and Application of Automata (CIAA 2015), Umeå, Sweden,
volume 9223 of Lecture Notes in Computer Science, pages 114--126.
Springer, 2015.
PDF venue official |
| • |
Hermann Gruber and Markus Holzer.
From Finite Automata to Regular Expressions and Back—A
Summary on Descriptional Complexity.
In Zoltán Ésik and Zoltán Fülöp, editors, 14th
International Conference on Automata and Formal Languages (AFL 2014), Szeged,
Hungary, volume 151 of Electronic Proceedings in Theoretical Computer
Science, pages 25--48, 2014.
PDF venue official |
| • |
Hermann Gruber, Adrien Richard, and Christophe Soulé.
How to Knock out Feedback Circuits in Gene Networks?
In Vincenzo Capasso, Mikhael Gromov, Annick Harel-Bellan, Nadya
Morozova, and Linda L. Pritchard, editors, Pattern Formation in
Morphogenesis --- Problems and Mathematical Issues, volume 15 of
Springer Proceedings in Mathematics, pages 175--178. Springer, 2013.
PDF venue official |
| • |
Hermann Gruber and Stefan Gulan.
Simplifying Regular Expressions. A Quantitative Perspective.
In Adrian-Horia Dediu, Henning Fernau, and Carlos Martín-Vide,
editors, 4th International Conference on Language and Automata Theory
and Applications (LATA 2010), Trier, Germany, volume 6031 of Lecture
Notes in Computer Science, pages 285--296. Springer, 2010.
PDF venue official |
| • |
Hermann Gruber, Markus Holzer, and Michael Tautschnig.
Short Regular Expressions from Finite Automata: Empirical
Results.
In Sebastian Maneth, editor, 14th International Conference on
Implementation and Application of Automata (CIAA 2009), Sydney, Australia,
volume 5642 of Lecture Notes in Computer Science, pages 188--197.
Springer, July 2009.
source code corrigendum PDF venue official |
| • |
Hermann Gruber, Markus Holzer, and Martin Kutrib.
On Measuring Non-Recursive Trade-Offs.
In Jürgen Dassow, Giovanni Pighizzini, and Bianca Truthe,
editors, 11th Workshop on Descriptional Complexity of Formal Systems
(DCFS 2009), Magdeburg, Germany, volume 3 of Electronic Proceedings in
Theoretical Computer Science, pages 141--150, July 2009.
PDF venue official |
| • |
Hermann Gruber and Markus Holzer.
Tight Bounds on the Descriptional Complexity of Regular
Expressions.
In Volker Diekert and Dirk Nowotka, editors, 13th International
Conference on Developments in Language Theory (DLT 2009), Stuttgart,
Germany, volume 5583 of Lecture Notes in Computer Science, pages
276--287. Springer, June--July 2009.
PDF venue official |
| • |
Hermann Gruber.
Digraph Complexity Measures and Applications in Formal Language
Theory.
In David Antoš, Milan Češka, Zdeněk Kotásek,
Mojmír Křetínský, Luděk Matyska, and Tomáš
Vojnar, editors, 4th Workshop on Mathematical and Engineering Methods in
Computer Science (MEMICS 2008), Znojmo, Czech Republic, pages 60--67,
November 2008.
PDF venue |
| • |
Hermann Gruber and Markus Holzer.
Provably Shorter Regular Expressions from Deterministic Finite
Automata (Extended Abstract).
In Masami Ito and Masafumi Toyama, editors, 12th International
Conference on Developments in Language Theory (DLT 2008), Kyoto, Japan,
volume 5257 of Lecture Notes in Computer Science, pages 383--395.
Springer, September 2008.
PDF venue official |
| • |
Hermann Gruber and Markus Holzer.
Language Operations with Regular Expressions of Polynomial
Size.
In Cezar Câmpeanu and Giovanni Pighizzini, editors, 10th
International Workshop on Descriptional Complexity of Formal Systems (DCFS
2008), Charlottetown (Prince Edward Island), Canada, pages 182--193. CSIT
University of Prince Edward Island, July 2008.
PDF venue |
| • |
Hermann Gruber and Markus Holzer.
Finite Automata, Digraph Connectivity, and Regular Expression
Size.
In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M.
Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors,
35th International Colloquium on Automata, Languages and Programming
(ICALP 2008), Reykjavik, Iceland, volume 5126 of Lecture Notes in
Computer Science, pages 39--50. Springer, July 2008.
PDF venue official |
| • |
Hermann Gruber and Jan Johannsen.
Optimal Lower Bounds on Regular Expression Size using
Communication Complexity.
In Roberto Amadio, editor, 11th International Conference on
Foundations of Software Science and Computation Structures 2008 (FoSSaCS
2008), member conference of the European Joint Conference on Theory and
Practice of Software 2008 (ETAPS 2008), Budapest, Hungary, volume 4962 of
Lecture Notes in Computer Science, pages 273--286. Springer, March
2008.
PDF venue official |
| • |
Hermann Gruber, Markus Holzer, and Martin Kutrib.
More on the Size of Higman-Haines Sets: Effective
Constructions.
In Jérôme Olivier Durand-Lose and Maurice Margenstern,
editors, 5th International Conference on Machines, Computations, and
Universality (MCU 2007), Orléans, France, volume 4664 of Lecture
Notes in Computer Science, pages 193--204, September 2007.
PDF venue official |
| • |
Hermann Gruber and Markus Holzer.
Inapproximability of Nondeterministic State and Transition
Complexity Assuming P <> NP.
In Terjo Harju, Juhani Karhumäki, and Arto Lepistö, editors,
11th International Conference on Developments in Language Theory (DLT
2007), Turku, Finland, volume 4588 of Lecture Notes in Computer
Science, pages 205--216, July 2007.
PDF venue official |
| • |
Hermann Gruber, Markus Holzer, and Oliver Ruepp.
Sorting the Slow Way: An Analysis of Perversely Awful Randomized
Sorting Algorithms.
In Pierluigi Crescenzi, Giuseppe Prencipe, and Geppino Pucci,
editors, 4th International Conference on Fun with Algorithms (FUN 2007),
Castiglioncello, Italy, volume 4475 of Lecture Notes in Computer
Science, pages 183--197, June 2007.
PDF venue official |
| • |
Hermann Gruber and Markus Holzer.
Computational Complexity of NFA Minimization for Finite and
Unary Languages.
In Remco Loos, Szilárd Zsolt Fazekas, and Carlos
Martín-Vide, editors, 1st International Conference on Language and
Automata Theory and Applications (LATA 2007), Tarragona, Spain, pages
261--272, March--April 2007.
PDF venue official |
| • |
Hermann Gruber and Markus Holzer.
Results on the average state and transition complexity of finite
automata accepting finite languages (Extended Abstract).
In Hing Leung and Giovanni Pighizzini, editors, 8th Workshop on
Descriptional Complexity of Formal Systems (DCFS 2006), Las Cruces (NM),
USA, Computer Science Technical Report NMSU-CS-2006-001, pages 267--275,
June 2006.
PDF venue |
| • |
Hermann Gruber and Markus Holzer.
Finding Lower Bounds for Nondeterministic State Complexity Is
Hard.
In Oscar H. Ibarra and Zhe Dang, editors, 10th International
Conference on Developments in Language Theory (DLT 2006), Santa Barbara (CA),
USA, volume 4036 of Lecture Notes in Computer Science, pages 363--374.
Springer, June 2006.
PDF venue official |
| • |
Hermann Gruber, Markus Holzer, Astrid Kiehn, and Barbara König.
On Timed Automata with Discrete Time—Structural and
Language Theoretical Characterization.
In Clelia de Felice and Antonio Restivo, editors, 9th
International Conference on Developments in Language Theory (DLT 2005),
Palermo, Italy, volume 3572 of Lecture Notes in Computer Science,
pages 272--283. Springer, July 2005.
PDF venue official |
| • |
Hermann Gruber, Markus Holzer, and Martin Kutrib.
Descriptional Complexity of Regular Languages.
In Jean-Eric Pin, editor, Handbook of Automata Theory. Volume I:
Theoretical Foundations, pages 411--458. European Mathematical Society
Press, 2021.
official |
| • |
Hermann Gruber, Jonathan Lee, and Jeffrey Shallit.
Enumerating Regular Expressions and Their Languages.
In Jean-Eric Pin, editor, Handbook of Automata Theory. Volume I:
Theoretical Foundations, pages 459--492. European Mathematical Society
Press, 2021.
official |
| • |
Hermann Gruber.
On the Descriptional and Algorithmic Complexity of Regular
Languages.
HARLAND Media, Lichtenberg (Odw.), Germany, 2010.
Dissertation, Justus-Liebig-Universität Giessen.
PDF (teaser) official |
| • |
Hermann Gruber, Markus Holzer, and Sebastian Jakobi.
More on Deterministic and Nondeterministic Finite Cover
Automata.
Theoretical Computer Science, 679:18--30, 2017.
PDF official |
| • |
Hermann Gruber and Markus Holzer.
From Finite Automata to Regular Expressions and Back—A
Summary on Descriptional Complexity.
International Journal of Foundations of Computer Science,
26(8):1009--1040, 2015.
PDF official |
| • |
Hermann Gruber and Markus Holzer.
Provably Shorter Regular Expressions From Finite Automata.
International Journal of Foundations of Computer Science,
24(8):1255--1279, 2013.
PDF official |
| • |
Hermann Gruber.
On Balanced Separators, Treewidth, and Cycle Rank.
Journal of Combinatorics, 3(4):669--682, 2012.
PDF official |
| • |
Hermann Gruber.
Digraph Complexity Measures and Applications in Formal Language
Theory.
Discrete Mathematics & Theoretical Computer Science,
14(2):189--204, 2012.
PDF official |
| • |
Hermann Gruber.
Bounding the Feedback Vertex Number of Digraphs in Terms of
Vertex Degrees.
Discrete Applied Mathematics, 159(8):872--875, 2011.
PDF official |
| • |
Hermann Gruber, Markus Holzer, and Martin Kutrib.
On Measuring Non-recursive Trade-offs.
Journal of Automata, Languages and Combinatorics,
15(1/2):107--120, 2010.
PDF official |
| • |
Hermann Gruber and Markus Holzer.
Language Operations with Regular Expressions of Polynomial
Size.
Theoretical Computer Science, 410(35):3281--3289, 2009.
PDF official |
| • |
Hermann Gruber, Markus Holzer, and Martin Kutrib.
More on the Size of Higman-Haines Sets: Effective
Constructions.
Fundamenta Informaticae, 91(1):105--121, 2009.
PDF official |
| • |
Hermann Gruber.
On Knot Polynomials of Annular Surfaces and their Boundary
Links.
Mathematical Proceedings of the Cambridge Philosophical
Society, 147(1):173--183, 2009.
PDF official |
| • |
Hermann Gruber and Markus Holzer.
On the Average State and Transition Complexity of Finite
Languages.
Theoretical Computer Science, 387(2):167--176, 2007.
PDF official |
| • |
Hermann Gruber, Markus Holzer, and Martin Kutrib.
The Size of Higman-Haines Sets.
Theoretical Computer Science, 387(2):155--166, 2007.
PDF official |
| • |
Hermann Gruber, Markus Holzer, and Simon Wolfsteiner.
On Minimizing Regular Expressions Without Kleene Star.
Technical Report ECCC TR20-079, Electronic Colloquium on
Computational Complexity, 2020.
official |
| • |
Hermann Gruber and Stefan Gulan.
Simplifying Regular Expressions: A Quantitative Perspective.
IFIG Research Report 0904, Institut für Informatik,
Justus-Liebig-Universität Giessen, August 2009.
|
| • |
Hermann Gruber and Markus Holzer.
Tight Bounds on the Descriptional Complexity of Regular
Expressions.
IFIG Research Report 0901, Institut für Informatik,
Justus-Liebig-Universität Giessen, February 2009.
|
| • |
Hermann Gruber and Markus Holzer.
Language Operations with Regular Expressions of Polynomial
Size.
Technical Report TUM-I0814, Institut für Informatik, Technische
Universität München, May 2008.
|
| • |
Hermann Gruber and Markus Holzer.
Provably Shorter Regular Expressions from Deterministic Finite
Automata.
Technical Report TUM-I0805, Institut für Informatik, Technische
Universität München, February 2008.
|
| • |
Hermann Gruber and Markus Holzer.
Finite Automata, Digraph Connectivity, and Regular Expression
Size.
Technical Report TUM-I0725, Institut für Informatik, Technische
Universität München, December 2007.
|
| • |
Hermann Gruber and Markus Holzer.
Finding Lower Bounds for Nondeterministic State Complexity is
Hard.
Technical Report ECCC TR06-027, Electronic Colloquium on
Computational Complexity, 2006.
official |
| • |
Hermann Gruber and Markus Holzer.
Optimal Regular Expressions for Palindromes of Given Length.
In Andreas Maletti, editor, 31. Theorietag der GI-Fachgruppe
0.1.5 "Automaten und Formale Sprachen", Leipzig, Germany (online), pages
23--26, 2021.
venue official |
| • |
Hermann Gruber, Markus Holzer, and Simon Wolfsteiner.
Concise Description of Finite Languages, Revisited.
In Henning Fernau, editor, 27. Theorietag der GI-Fachgruppe
0.1.5 "Automaten und Formale Sprachen", Bonn, Germany, Technical Reports
Mathematics/Computer Science No. 17-1, pages 32--36. Universität Trier,
Germany, 2017.
PDF venue |
| • |
Hermann Gruber, Jonathan Lee, and Jeffrey Shallit.
Enumerating Regular Expressions and their Languages.
available online at arxiv.org as arXiv:1204.4982, 2012.
|
| • |
Hermann Gruber.
On Balanced Separators, Treewidth, and Cycle Rank.
available online at arxiv.org as arXiv:1012.1344, 2010.
|
| • |
Hermann Gruber and Stefan Gulan.
Simplifying Regular Expressions: A Quantitative Perspective.
In Jöran Mielke, Ludwig Staiger, and Renate Winter, editors,
19. Theorietag der GI-Fachgruppe 0.1.5 "Automaten und Formale Sprachen",
Wittenberg, Germany, Institute of Computer Science Technical Report 2009/03,
pages 30--31. Universität Halle-Wittenberg, Germany, September 2009.
PDF venue |
| • |
Hermann Gruber, Markus Holzer, and Martin Kutrib.
On Measuring Non-Recursive Trade-Offs.
In Jöran Mielke, Ludwig Staiger, and Renate Winter, editors,
19. Theorietag der GI-Fachgruppe 0.1.5 "Automaten und Formale Sprachen",
Wittenberg, Germany, Institute of Computer Science Technical Report 2009/03,
pages 32--35. Universität Halle-Wittenberg, Germany, September 2009.
PDF venue |
| • |
Hermann Gruber and Markus Holzer.
Kürzere reguläre Ausdrücke aus deterministischen
endlichen Automaten.
FORMAT Workshop Spring 2009, Universität Würzburg, Germany,
February 2009.
PDF venue |
| • |
Hermann Gruber.
On the D-width of Directed Graphs.
Manuscript, 7 pages, February 2008.
|
| • |
Hermann Gruber and Jan Johannsen.
Communication Complexity and Regular Expression Size.
In Markus Holzer, Martin Kutrib, and Andreas Malcher, editors,
18. Theorietag der GI-Fachgruppe 0.1.5 "Automaten und Formale Sprachen",
Launsbach-Wettenberg, Germany, IFIG Research Report 0801, pages 61--66.
Universität Giessen, Germany, 2008.
PDF venue |
| • |
Hermann Gruber and Markus Holzer.
Language Operations with Regular Expressions of Polynomial
Size.
In Markus Holzer, Martin Kutrib, and Andreas Malcher, editors,
18. Theorietag der GI-Fachgruppe 0.1.5 "Automaten und Formale Sprachen",
Launsbach-Wettenberg, Germany, IFIG Research Report 0801, pages 73--76.
Universität Giessen, Germany, 2008.
PDF venue |
| • |
Hermann Gruber, Markus Holzer, and Martin Kutrib.
On the Size of Higman-Haines Sets.
In Manfred Droste and Markus Lohrey, editors, 17. Theorietag der
GI-Fachgruppe 0.1.5 "Automaten und Formale Sprachen", Leipzig, Germany,
pages 65--67. Universität Leipzig, Germany, 2007.
PDF venue |
| • |
Hermann Gruber and Markus Holzer.
Results on the Average State and Transition Complexity of Finite
Automata Accepting Finite Languages.
In Rudolf Freund and Marion Oswald, editors, 16. Theorietag der
GI-Fachgruppe 0.1.5 "Automaten und Formale Sprachen", Vienna, Austria.
Technische Universität Wien, Austria, 2006.
PDF venue |
| • |
Hermann Gruber and Markus Holzer.
Finding Upper Bounds for Nondeterministic State Complexity is
Hard.
In Rudolf Freund and Marion Oswald, editors, 16. Theorietag der
GI-Fachgruppe 0.1.5 "Automaten und Formale Sprachen", Vienna, Austria.
Technische Universität Wien, Austria, 2006.
PDF venue |
| • |
Hermann Gruber and Markus Holzer.
A note on the number of transitions of nondeterministic finite
automata.
In Henning Fernau, editor, 15. Theorietag der GI-Fachgruppe
0.1.5 "Automaten und Formale Sprachen", Lauterbad, Germany. Universität
Tübingen, Germany, 2005.
PDF venue |
| • |
Hermann Gruber, Markus Holzer, Astrid Kiehn, and Barbara König.
On Timed Automata with Discrete Time - Structural and Language
Theoretical Characterization.
In Suna Bensch, Oliver Boldt, Henning Bordihn, and Helmut
Jürgensen, editors, 14. Theorietag der GI-Fachgruppe 0.1.5
"Automaten und Formale Sprachen", Caputh, Germany. Universität Potsdam,
Germany, 2004.
PS venue |
| • |
Hermann Gruber.
Estimates for the minimal crossing number.
available online at arxiv.org as math.GT/0303273v3, 2003.
|
Parts of this page were automatically generated with bibtex2html 1.92
| Zurück zu Hermann Gruber |