Author name cluster

Robert Giegerich

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

TCS Journal 2013 Journal Article

Forest alignment with affine gaps and anchors, applied in RNA structure comparison

Stefanie Schirmer
Robert Giegerich

We present two enhancements to Jiang’s tree alignment algorithm, motivated by experience with its use for RNA structure alignment. One enhancement is the introduction of an affine gap model, which can be accommodated with a runtime increase by a constant factor. The second enhancement is a speed-up of the alignment algorithm when certain nodes in the trees are pre-aligned by a so-called anchoring. Both enhancements are included in a new implementation of the tool RNAforester. We evaluate the new algorithm with two applications related to RNA secondary structure analysis. Based on our experience, we suggest a new formulation of the tree alignment model, based on regular tree languages and rewrite rules.

Details DOI

I&C Journal 2006 Journal Article

Table design in dynamic programming

Peter Steffen
Robert Giegerich

Dynamic Programming solves combinatorial optimization problems by recursive decomposition and tabulation of intermediate results. The first step in the design of a dynamic programming algorithm is to decide on the set of tables that will hold optimal solutions to subproblems. This step predetermines the shape of the dynamic programming recurrences as well as the asymptotic efficiency of the algorithm in time and space. We study dynamic programming in a formal framework where design of tables and problem decomposition can be done independently. Our main result shows that choosing a good table design for a given decomposition is an NP-complete problem. A heuristic or approximate approach is therefore needed to automate good table design. We report on a strategy that combines user annotation and a brute force algorithm, which is shown to perform well in a large application.

Details DOI

TCS Journal 1990 Journal Article

Code selection by inversion of order-sorted derivors

Robert Giegerich

The goal of this work is to provide a general framework for the pattern matching approach to the code selection problem with the following properties: recent approaches can be reformulated and compared in this framework, it accommodates increased expressive power for defining intermediate languages, it provides formal criteria for the completeness of a code selector specification, it uses a straightforward generalization of known pattern matching techniques, it offers a new way to integrate the “nonsyntactic” subtasks of code generation with the pattern matching process. These properties are achieved by formulating pattern matching as the problem of constructing an inverse to a hierarchic derivor between order-sorted term algebras.

Details DOI