---
res:
  bibo_abstract:
  - Streaming string transducers [1] define (partial) functions from input strings
    to output strings. A streaming string transducer makes a single pass through the
    input string and uses a finite set of variables that range over strings from the
    output alphabet. At every step, the transducer processes an input symbol, and
    updates all the variables in parallel using assignments whose right-hand-sides
    are concatenations of output symbols and variables with the restriction that a
    variable can be used at most once in a right-hand-side expression. It has been
    shown that streaming string transducers operating on strings over infinite data
    domains are of interest in algorithmic verification of list-processing programs,
    as they lead to PSPACE decision procedures for checking pre/post conditions and
    for checking semantic equivalence, for a well-defined class of heap-manipulating
    programs. In order to understand the theoretical expressiveness of streaming transducers,
    we focus on streaming transducers processing strings over finite alphabets, given
    the existence of a robust and well-studied class of "regular" transductions
    for this case. Such regular transductions can be defined either by two-way deterministic
    finite-state transducers, or using a logical MSO-based characterization. Our main
    result is that the expressiveness of streaming string transducers coincides exactly
    with this class of regular transductions. @eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Rajeev
      foaf_name: Alur, Rajeev
      foaf_surname: Alur
  - foaf_Person:
      foaf_givenName: Pavol
      foaf_name: Cerny, Pavol
      foaf_surname: Cerny
      foaf_workInfoHomepage: http://www.librecat.org/personId=4DCBEFFE-F248-11E8-B48F-1D18A9856A87
  bibo_doi: 10.4230/LIPIcs.FSTTCS.2010.1
  bibo_volume: 8
  dct_date: 2010^xs_gYear
  dct_identifier:
  - UT:000310361000001
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: Expressiveness of streaming string transducers@
...