FB 07 - Mathematik und Informatik, Physik, Geographie

Dauerhafte URI für den Bereich

jlupub.ub.uni-giessen.de/handle/jlupub/1037

Stöbern nach

Auflistung FB 07 - Mathematik und Informatik, Physik, Geographie nach Autor:in "Gruber, Hermann"

Gerade angezeigt 1 - 3 von 3
  • Vorschaubild
    Item
    On Pumping Preserving Homomorphisms and the Complexity of the Pumping Problem
    (2024-06-27) Gruber, Hermann; Holzer, Markus; Rauch, Christian
    This paper complements a recent inapproximability result for the minimal pumping constant w.r.t. a fixed regular pumping lemma for nondeterministic finite automata [H. Gruber and M. Holzer and C. Rauch. The Pumping Lemma for Regular Languages is Hard. CIAA 2023, pp. 128-140.], by showing the inapproximability of this problem even for deterministic finite automata, and at the same time proving stronger lower bound on the attainable approximation ratio, assuming the Exponential Time Hypothesis (ETH). To that end, we describe those homomorphisms that, in a precise sense, preserve the respective pumping arguments used in two different pumping lemmata. We show that, perhaps surprisingly, this concept coincides with the classic notion of star height preserving homomorphisms as studied by McNaughton, and by Hashiguchi and Honda in the 1970s. Also, we gain a complete understanding of the minimal pumping constant for bideterministic finite automata, which may be of independent interest.
  • Vorschaubild
    Item
    Simplifying regular expressions : A quantitative perspective
    (2009) Gruber, Hermann; Gulan, Stefan
    In this work, we consider the efficient simplification of regular expressions. We suggest a quantitative comparison of heuristics for simplifying regular expressions. We propose a new normal form for regular expressions, which outperforms previous heuristics while still being computable in linear time. We apply this normal form to determine an exact bound for the relation between the two most common size measures for regular expressions, namely alphabetic width and reverse polish notation length. Then we proceed to show that every regular expression of alphabetic with n can be converted into a nondeterministic finite automaton with e-transitions of size at most 42 5n + 1, and that this bound is optimal. This provides an exact resolution of a research problem posed by Ilie and Yu, who had obtained lower and upper bounds of 4n -1 and 9n - 1 2, respectively [L. Ilie, S. Yu: Follow automata. Inform. Comput. 186, 2003]. For reverse polish notation length as input size measure, an optimal bound was recently determined [S. Gulan, H. Fernau: An optimal construction of finite automata from regular expressions. In: Proc. FST & TCS, 2008]. We prove that, under mild restrictions, their construction is also optimal when taking alphabetic width as input size measure.
  • Vorschaubild
    Item
    Tight bounds on the descriptional complexity of regular expressions
    (2009) Gruber, Hermann; Holzer, Markus
    We improve on some recent results on lower bounds for conversion problems for regular expressions. In particular we consider the conversion of planar deterministic finite automata to regular expressions, study the effect of the complementation operation on the descriptional complexity of regular expressions, and the conversion of regular expressions extended by adding intersection or interleaving to ordinary regular expressions. Almost all obtained lower bounds are optimal, and the presented examples are over a binary alphabet, which is best possible.