  Streaming Data String Transducers (SDSTs) were introduced to model a class of
imperative and a class of functional programs, manipulating lists of data
items. These can be used to write commonly used routines such as insert, delete
and reverse. SDSTs can handle data values from a potentially infinite data
domain. The model of Streaming String Transducers (SSTs) is the fragment of
SDSTs where the infinite data domain is dropped and only finite alphabets are
considered. SSTs have been much studied from a language theoretical point of
view. We introduce data back into SSTs, just like data was introduced to finite
state automata to get register automata. The result is Streaming String
Register Transducers (SSRTs), which is a subclass of SDSTs. SDSTs can compare
data values using a linear order on the data domain, which can not be done by
SSRTs.
  We give a machine independent characterization of SSRTs with origin
semantics, along the lines of Myhill-Nerode theorem. Machine independent
characterizations for similar models have formed the basis of learning
algorithms and enabled us to understand fragments of the models. Origin
semantics of transducers track which positions of the output originate from
which positions of the input. Although a restriction, using origin semantics is
well justified and known to simplify many problems related to transducers. We
use origin semantics as a technical building block, in addition to
characterizations of deterministic register automata. However, we need to build
more on top of these to overcome some challenges unique to SSRTs.
