Return to search

Visibly pushdown transducers

The present work proposes visibly pushdown transducers (VPTs) for defining transformations of documents with a nesting structure. We show that this subclass of pushdown transducers enjoy good properties. Notably, we show that functionality is decidable in PTime and k-valuedness in co-NPTime. While this class is not closed under composition and its type checking problem against visibly pushdown automata is undecidable, we identify a subclass, the well-nested VPTs, closed under composition and with a decidable type checking problem. Furthermore, we show that the class of VPTs is closed under look-ahead, and that the deterministic VPTs with look-ahead characterize the functional VPTs transductions. Finally, we investigate the resources necessary to perform transformations defined by VPTs. We devise a memory efficient algorithm. Then we show that it is decidable whether a VPT transduction can be performed with a memory that depends on the level of nesting of the input document but not on its length. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

Identiferoai:union.ndltd.org:ulb.ac.be/oai:dipot.ulb.ac.be:2013/209865
Date26 September 2011
CreatorsServais, Frédéric
ContributorsRaskin, Jean-François, Vansummeren, Stijn, Alur, Rajeev, Filiot, Emmanuel, Maneth, Sebastian, Neven, Frank, Zimanyi, Esteban
PublisherUniversite Libre de Bruxelles, Université libre de Bruxelles, Ecole polytechnique de Bruxelles – Informatique, Bruxelles
Source SetsUniversité libre de Bruxelles
LanguageFrench
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/doctoralThesis, info:ulb-repo/semantics/doctoralThesis, info:ulb-repo/semantics/openurl/vlink-dissertation
Format1 v. (ix, 202 p.), No full-text files

Page generated in 0.0023 seconds