Computer Science – Programming Languages
Scientific paper
2007-01-26
Computer Science
Programming Languages
Scientific paper
Macro tree transducers (mtt) are an important model that both covers many useful XML transformations and allows decidable exact typechecking. This paper reports our first step toward an implementation of mtt typechecker that has a practical efficiency. Our approach is to represent an input type obtained from a backward inference as an alternating tree automaton, in a style similar to Tozawa's XSLT0 typechecking. In this approach, typechecking reduces to checking emptiness of an alternating tree automaton. We propose several optimizations (Cartesian factorization, state partitioning) on the backward inference process in order to produce much smaller alternating tree automata than the naive algorithm, and we present our efficient algorithm for checking emptiness of alternating tree automata, where we exploit the explicit representation of alternation for local optimizations. Our preliminary experiments confirm that our algorithm has a practical performance that can typecheck simple transformations with respect to the full XHTML in a reasonable time.
Frisch Alain
Hosoya Haruo
No associations
LandOfFree
Towards Practical Typechecking for Macro Tree Transducers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Towards Practical Typechecking for Macro Tree Transducers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Towards Practical Typechecking for Macro Tree Transducers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-568238