Expressiveness of streaming string transducers

Alur R, Cerny P. 2010. Expressiveness of streaming string transducers. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 8, 1–12.

Download
OA IST-2018-948-v1+1_2011_Cerny_Expressiveness_of.pdf 492.34 KB [Published Version]

Conference Paper | Published | English

Scopus indexed
Author
Alur, Rajeev; Cerny, PavolISTA

Corresponding author has ISTA affiliation

Series Title
LIPIcs
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.
Publishing Year
Date Published
2010-01-01
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume
8
Page
1 - 12
Conference
FSTTCS: Foundations of Software Technology and Theoretical Computer Science
Conference Location
Chennai, India
Conference Date
2010-12-15 – 2010-12-18
IST-REx-ID
488

Cite this

Alur R, Cerny P. Expressiveness of streaming string transducers. In: Vol 8. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2010:1-12. doi:10.4230/LIPIcs.FSTTCS.2010.1
Alur, R., & 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. https://doi.org/10.4230/LIPIcs.FSTTCS.2010.1
Alur, Rajeev, and Pavol Cerny. “Expressiveness of Streaming String Transducers,” 8:1–12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. https://doi.org/10.4230/LIPIcs.FSTTCS.2010.1.
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.
Alur R, Cerny P. 2010. Expressiveness of streaming string transducers. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 8, 1–12.
Alur, Rajeev, and Pavol Cerny. Expressiveness of Streaming String Transducers. Vol. 8, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 1–12, doi:10.4230/LIPIcs.FSTTCS.2010.1.
All files available under the following license(s):
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0):
Main File(s)
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
5845be5aa19791830f7407d8853f2df0


Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar