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 metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00566291
Contributor : Joachim Niehren <>
Submitted on : Tuesday, March 1, 2011 - 12:37:40 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on: Monday, May 30, 2011 - 2:16:45 AM

File

lata-final.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00566291, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

505

Files downloads

372