Books

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

Journal Articles

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

Conference Papers

Hermann Gruber and Markus Holzer. From Finite Automata to Regular Expressions and Back—A Summary on Descriptional Complexity. In 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  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  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

Technical Reports

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.
PDF
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.
PDF
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.
PDF
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.
PDF
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.
PDF
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

Other Works (non-refereed)

Hermann Gruber, Jonathan Lee, and Jeffrey Shallit. Enumerating Regular Expressions and their Languages. available online at arxiv.org as arXiv:1204.4982, 2012.
PDF
Hermann Gruber. On Balanced Separators, Treewidth, and Cycle Rank. available online at arxiv.org as arXiv:1012.1344, 2010.
PDF
Hermann Gruber and Stefan Gulan. Simplifying Regular Expressions: A Quantitative Perspective. In 19. Theorietag der GI-Fachgruppe 0.1.5 "Automaten und Formale Sprachen", Wittenberg, Germany. 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.
PDF
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. 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. 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. 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.
PDF

Parts of this page were automatically generated with bibtex2html 1.92

  Zurück zu Hermann Gruber