7 citations · 19 across the 5 of their papers we have counts for
8 papers
From Finite Automata to Regular Expressions and Back--A Summary on Descriptional Complexity
Hermann Gruber, Markus Holzer
The equivalence of finite automata and regular expressions dates back to the seminal paper of Kleene on events in nerve nets and finite automata from 1956. In the present paper we…
Enumerating regular expressions and their languages
Hermann Gruber, Jonathan Lee, Jeffrey Shallit
In this chapter we discuss the problem of enumerating distinct regular expressions by size and the regular languages they represent. We discuss various notions of the size of a reg…
Digraph Complexity Measures and Applications in Formal Language Theory
Hermann Gruber
We investigate structural complexity measures on digraphs, in particular the cycle rank. This concept is intimately related to a classical topic in formal language theory, namely t…
Bounding the Feedback Vertex Number of Digraphs in Terms of Vertex Degrees
Hermann Gruber
The Turan bound is a famous result in graph theory, which relates the independence number of an undirected graph to its edge density. Also the Caro-Wei inequality, which gives a mo…
On Balanced Separators, Treewidth, and Cycle Rank
Hermann Gruber
We investigate relations between different width parameters of graphs, in particular balanced separator number, treewidth, and cycle rank. Our main result states that a graph with…
On Measuring Non-Recursive Trade-Offs
Hermann Gruber, Markus Holzer, Martin Kutrib
We investigate the phenomenon of non-recursive trade-offs between descriptional systems in an abstract fashion. We aim at categorizing non-recursive trade-offs by bounds on their g…