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.
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 and Markus Holzer. Provably Shorter Regular Expressions From Finite Automata. International Journal of Foundations of Computer Science, 2013. Accepted for publication subject to minor revision. |
| • |
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, 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 LNCS,
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 LNCS, 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 LNCS, 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 LNCS, 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 LNCS, 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
LNCS, 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 LNCS,
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 LNCS, 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 LNCS, 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 LNCS, 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 LNCS, pages 272-283. Springer, July
2005.
PDF venue 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.
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 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.
|
| • |
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.
|
Parts of this page were automatically generated with bibtex2html 1.92
| Zurück zu Hermann Gruber |