Institute of Computer Languages
Compilers and Languages Group

Talks 2006 - Oliver Rüthing

The Compilers and Languages Group invites you to a talk given by

Dr. Oliver Rüthing

Universität Dortmund, Deutschland on

Erkennen Herbrand-äquivalenter Berechnungen - Stand, Entwicklung und Grenzen

Date: Friday, January 27th, 2006
Time: 15:00 (s.t.)
Location: TU Wien, Elektrotechnik, Reithoffer Hörsaal, Gusshausstraße 25-29 (Altbau), 2. Stock

Abstract:

Das Erkennen wertegleicher Berechnungen in Programmen ist von Bedeutung in zahlreichen Anwendungsfeldern. Insbesondere kann in optimierenden Compilern die Information über wertegleiche Berechnungen ausgenutzt werden, um die Wirkung von Optimierungstransformationen wie Partielle Redundanzelimination, Konstantenpropagation oder Elimination toten Codes zu erhöhen.

Das Problem, die Wertegleichheit von Ausdrücken an einer Programmstelle festzustellen, ist bekanntermassen unentscheidbar. Dieses gilt selbst dann, wenn die Bedingungen des Programms nicht interpretiert werden. Aus diesem Grunde betrachtet man oft vereinfachte Modelle, in denen eine Teilklasse aller gültigen Gleichheiten entschieden werden kann. Ein besonders interessantes Szenario dieser Art bilden Gleichheiten zwischen Berechnungen, die unabhängig von den zugrunde liegenden Operatoreigenschaften gelten, sogenannte Herbrand-äquivalente Berechnungen.

Der Vortrag gibt zunächst einen Überblick über verschiedene klassische Verfahren in dem Bereich und diskutiert insbesondere Aspekte der Vollständigkeit und Komplexität. Anschliessend werden einige neuere Resultate beleuchtet. So wird gezeigt, dass Herbrand-äquivalente Berechnungen in polynomieller Zeit bestimmt werden können. Darüber hinaus wird ein neuer Anfrage-basierter Ansatz vorgestellt, mit dem beliebige positive Boolesche Kombinationen von Herbrand-Gleichheiten entschieden werden können, auch dann, wenn Tests auf Ungleichheit berücksichtigt werden.

About Dr. Rüthing

Oliver Rüthing graduated (1991) and obtained a PhD in Computer Science (1997) at the Christian-Albrechts University Kiel. Since 1997 he is research associate at the University of Dortmund. In 2004 he was guest lecturer at the International University of Bremen. His research is focused on the areas of programming languages, compiler construction and program analysis.
Complang
   About Us
   Research
   Lehre
   Service
      Robotics
      Library
      Talks 2017
      Talks 2016
      Talks 2015
      Talks 2014
      Talks 2013
      Talks 2012
      Talks 2011
      Talks 2010
      Talks 2009
      Talks 2008
      Talks 2007
      Talks 2006
      Talks 2005
      Talks 2004
Sitemap
Contact
Fast Access:
Previous Talk
Next Talk
Faculty of Informatics
Vienna University of Technology
top | HTML 4.01 | last update: 2017-02-13 (Webmaster)