Главная

Rajeev Alur

  1. Regular Functions, Cost Register Automata, and Generalized Min-Cost Problems.

    Пт, 11/04/2011 - 15:01 — SomNambul
    Authors: Rajeev Alur, Loris D'Antoni, Jyotirmoy V. Deshmukh, Mukund Raghothaman, Yifei Yuan
    Subjects: Formal Languages and Automata Theory
    Abstract

    Motivated by the successful application of the theory of regular languages to
    formal verification of finite-state systems, there is a renewed interest in
    developing a theory of analyzable functions from strings to numerical values
    that can provide a foundation for analyzing {\em quantitative} properties of
    finite-state systems.

  2. Streaming Tree Transducers.

    Пт, 04/15/2011 - 15:01 — SomNambul
    Authors: Rajeev Alur, Loris D'Antoni
    Subjects: Formal Languages and Automata Theory
    Abstract

    We introduce streaming tree transducers as an analyzable and expressive model
    for transforming hierarchically structured data in a single pass. Given a
    linear encoding of the input tree, the transducer makes a single left-to-right
    pass through the input, and computes the linear encoding of the output tree in
    linear time using a finite-state control, a finite number of string variables,
    and a visibly pushdown stack.

  3. Algorithmic Verification of Single-Pass List Processing Programs.

    Чт, 07/29/2010 - 15:01 — SomNambul
    Authors: Rajeev Alur, Pavol Cerny
    Subjects: Programming Languages
    Abstract

    We identify a class of programs manipulating lists of data items for which
    checking functional equivalence and pre/post verification conditions is
    decidable. Lists are modeled as data words, (unbounded) sequences of data
    values, tagged with symbols from a finite set, over a potentially infinite data
    domain that supports only the operations of equality and ordering. First, we
    introduce streaming data-word transducers that map input data words to output
    data words in a single left-to-right pass in linear time.

Math-arch

RSS-материал