Skip to Main content Skip to Navigation
New interface
Conference papers

Normalization of Sequential Top-Down Tree-to-Word Transducers

Abstract : We study normalization of deterministic sequential top-down tree-to-word transducers (STWs), that capture the class of deterministic top-down nested-word to word transducers. We identify the subclass of earliest STWs (eSTWs) that yield normal forms when minimized. The main result of this paper is an effective normalization procedure for STWs. It consists of two stages: we first convert a given STW to an equivalent eSTW, and then, we minimize the eSTW.

Keywords: formal language theory, tree automata, transformations, XML databases, XSLT

Extended Version:

A long version is available here.

Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Joachim Niehren Connect in order to contact the contributor
Submitted on : Tuesday, March 1, 2011 - 12:37:40 PM
Last modification on : Friday, February 4, 2022 - 3:17:39 AM
Long-term archiving on: : Monday, May 30, 2011 - 2:16:45 AM


Files produced by the author(s)


  • HAL Id : inria-00566291, version 1



Grégoire Laurence, Aurélien Lemay, Joachim Niehren, Slawomir Staworko, Marc Tommasi. Normalization of Sequential Top-Down Tree-to-Word Transducers. 5th International Conference on Language Automata Theory and Appliciations, May 2011, Tarragona, Spain. ⟨inria-00566291⟩



Record views


Files downloads