@inproceedings{10.1007/978-3-642-22012-8_1,
    Abstract = {We introduce nondeterministic streaming string transducers (nssts) -- a new computational model that can implement MSO-definable relations between strings. An nsst makes a single left-to-right pass on the input string and uses a finite set of string variables to compute the output. In each step, it reads one input symbol, and updates its string variables in parallel with a copyless assignment. We show that nsst are closed under sequential composition and that their expressive power coincides with that of nondeterministic MSO-definable transductions. Further, we identify the class of functionalnssts; such an nsst allows nondeterministic transitions, but for every successful run on a given input generates the same output string. We show that deciding functionality of an arbitrary nsst is decidable with pspace complexity, while the equivalence problem for functional nssts is pspace-complete. We also show that checking if the set of outputs of an nsst is contained within the set of outputs of a finite number of dssts is decidable in pspace.},
    Address = {Berlin, Heidelberg},
    Author = {Alur, Rajeev and Deshmukh, Jyotirmoy V.},
    BookTitle = {Automata, Languages and Programming},
    Editor = {Aceto, Luca and Henzinger, Monika and Sgall, Ji{\v{r}}{\'\i}},
    File = {Nondeterministic Streaming String Transducers - Alur-Deshmukh2011\_Chapter\_NondeterministicStreamingStrin.pdf},
    ISBN = {978-3-642-22012-8},
    Pages = {1--20},
    Publisher = {Springer Berlin Heidelberg},
    Title = {Nondeterministic Streaming String Transducers},
    Year = {2011},
    date-added = {2022-05-26 15:28:51 +0200},
    date-modified = {2022-05-26 15:28:51 +0200},
    doi = {10.1007/978-3-642-22012-8_1}
}

@inproceedings{10.1007/978-3-642-22012-8_1, Abstract = {We introduce nondeterministic streaming string transducers (nssts) -- a new computational model that can implement MSO-definable relations between strings. An nsst makes a single left-to-right pass on the input string and uses a finite set of string variables to compute the output. In each step, it reads one input symbol, and updates its string variables in parallel with a copyless assignment. We show that nsst are closed under sequential composition and that their expressive power coincides with that of nondeterministic MSO-definable transductions. Further, we identify the class of functionalnssts; such an nsst allows nondeterministic transitions, but for every successful run on a given input generates the same output string. We show that deciding functionality of an arbitrary nsst is decidable with pspace complexity, while the equivalence problem for functional nssts is pspace-complete. We also show that checking if the set of outputs of an nsst is contained within the set of outputs of a finite number of dssts is decidable in pspace.}, Address = {Berlin, Heidelberg}, Author = {Alur, Rajeev and Deshmukh, Jyotirmoy V.}, BookTitle = {Automata, Languages and Programming}, Editor = {Aceto, Luca and Henzinger, Monika and Sgall, Ji{\v{r}}{\'\i}}, File = {Nondeterministic Streaming String Transducers - Alur-Deshmukh2011_Chapter_NondeterministicStreamingStrin.pdf}, ISBN = {978-3-642-22012-8}, Pages = {1--20}, Publisher = {Springer Berlin Heidelberg}, Title = {Nondeterministic Streaming String Transducers}, Year = {2011}, date-added = {2022-05-26 15:28:51 +0200}, date-modified = {2022-05-26 15:28:51 +0200}, doi = {10.1007/978-3-642-22012-8_1} }