Главная

Amir M. Ben-Amram

  1. On Decidable Growth-Rate Properties of Imperative Programs.

    Ср, 05/05/2010 - 15:01 — SomNambul
    Authors: Amir M. Ben-Amram
    Subjects: Logic in Computer Science
    Abstract

    In 2008, Ben-Amram, Jones and Kristiansen showed that for a simple "core"
    programming language - an imperative language with bounded loops, and
    arithmetics limited to addition and multiplication - it was possible to decide
    precisely whether a program had certain growth-rate properties, namely
    polynomial (or linear) bounds on computed values, or on the running time.

    This work emphasized the role of the core language in mitigating the
    notorious undecidability of program properties, so that one deals with
    decidable problems.

  2. The Euler Path to Static Level-Ancestors.

    Втр, 09/08/2009 - 12:16 — SomNambul
    Authors: Amir M. Ben-Amram
    Subjects: Data Structures and Algorithms
    Abstract

    Suppose that a rooted tree T is given for preprocessing. The Level-Ancestor
    Problem is to answer quickly queries of the following form. Given a vertex v
    and an integer i > 0, find the i-th vertex on the path from the root to v.
    Algorithms that achieve a linear time bound for preprocessing and a constant
    time bound for a query have been published by Dietz (1991), Alstrup and Holm
    (2000), and Bender and Farach (2002). The first two algorithms address dynamic
    versions of the problem; the last addresses the static version only and is the
    simplest so far.

Math-arch

RSS-материал