Algorithmic Verification of Single-Pass List Processing Programs

Rajeev Alur, Pavol Cerny

We introduce streaming data string transducers that map input data strings to output data strings in a single left-to-right pass in linear time. Data strings are (unbounded) sequen…