Symbolic Tree Transducers

Margus Veanes and Nikolaj Bjorner

Abstract

Symbolic transducers are useful in the context of web security as they form the foundation for sanitization of potentially malicious data. We define Symbolic Tree Transducers as a generalization of Regular Transducers as finite state input-output tree automata with logical constraints over a parametric background theory. We examine key closure properties of Symbolic Tree Transducers and we develop a composition algorithm and an equivalence decision procedure for linear single-valued transducers.

Details

Publication typeInproceedings
Published inErshov Informatics Conference (PSI'11)
Pages371-387
Volume7162
SeriesLNCS
PublisherSpringer
> Publications > Symbolic Tree Transducers