---
_id: '488'
abstract:
- lang: eng
  text: '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. '
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Rajeev
  full_name: Alur, Rajeev
  last_name: Alur
- first_name: Pavol
  full_name: Cerny, Pavol
  id: 4DCBEFFE-F248-11E8-B48F-1D18A9856A87
  last_name: Cerny
citation:
  ama: 'Alur R, Cerny P. Expressiveness of streaming string transducers. In: Vol 8.
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2010:1-12. doi:<a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2010.1">10.4230/LIPIcs.FSTTCS.2010.1</a>'
  apa: 'Alur, R., &#38; Cerny, P. (2010). Expressiveness of streaming string transducers
    (Vol. 8, pp. 1–12). Presented at the FSTTCS: Foundations of Software Technology
    and Theoretical Computer Science, Chennai, India: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2010.1">https://doi.org/10.4230/LIPIcs.FSTTCS.2010.1</a>'
  chicago: Alur, Rajeev, and Pavol Cerny. “Expressiveness of Streaming String Transducers,”
    8:1–12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. <a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2010.1">https://doi.org/10.4230/LIPIcs.FSTTCS.2010.1</a>.
  ieee: 'R. Alur and P. Cerny, “Expressiveness of streaming string transducers,” presented
    at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science,
    Chennai, India, 2010, vol. 8, pp. 1–12.'
  ista: 'Alur R, Cerny P. 2010. Expressiveness of streaming string transducers. FSTTCS:
    Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol.
    8, 1–12.'
  mla: Alur, Rajeev, and Pavol Cerny. <i>Expressiveness of Streaming String Transducers</i>.
    Vol. 8, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 1–12, doi:<a
    href="https://doi.org/10.4230/LIPIcs.FSTTCS.2010.1">10.4230/LIPIcs.FSTTCS.2010.1</a>.
  short: R. Alur, P. Cerny, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2010, pp. 1–12.
conference:
  end_date: 2010-12-18
  location: Chennai, India
  name: 'FSTTCS: Foundations of Software Technology and Theoretical Computer Science'
  start_date: 2010-12-15
corr_author: '1'
date_created: 2018-12-11T11:46:45Z
date_published: 2010-01-01T00:00:00Z
date_updated: 2025-09-30T09:49:32Z
day: '01'
ddc:
- '005'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.FSTTCS.2010.1
external_id:
  isi:
  - '000310361000001'
file:
- access_level: open_access
  checksum: 5845be5aa19791830f7407d8853f2df0
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:08:29Z
  date_updated: 2020-07-14T12:46:35Z
  file_id: '4690'
  file_name: IST-2018-948-v1+1_2011_Cerny_Expressiveness_of.pdf
  file_size: 492344
  relation: main_file
file_date_updated: 2020-07-14T12:46:35Z
has_accepted_license: '1'
intvolume: '         8'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 1 - 12
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7331'
pubrep_id: '948'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Expressiveness of streaming string transducers
tmp:
  image: /images/cc_by_nc_nd.png
  legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
  name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
    (CC BY-NC-ND 4.0)
  short: CC BY-NC-ND (4.0)
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 8
year: '2010'
...