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
| Identifer | oai:union.ndltd.org:ulb.ac.be/oai:dipot.ulb.ac.be:2013/209865 |
| Date | 26 September 2011 |
| Creators | Servais, Frédéric |
| Contributors | Raskin, Jean-François, Vansummeren, Stijn, Alur, Rajeev, Filiot, Emmanuel, Maneth, Sebastian, Neven, Frank, Zimanyi, Esteban |
| Publisher | Universite Libre de Bruxelles, Université libre de Bruxelles, Ecole polytechnique de Bruxelles – Informatique, Bruxelles |
| Source Sets | Université libre de Bruxelles |
| Language | French |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis, info:ulb-repo/semantics/doctoralThesis, info:ulb-repo/semantics/openurl/vlink-dissertation |
| Format | 1 v. (ix, 202 p.), No full-text files |
Page generated in 0.0028 seconds