Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/13187
Full metadata record
DC FieldValueLanguage
dc.contributor.authorSERVAIS, Frederic-
dc.contributor.authorFiliot, Emmanuel-
dc.contributor.authorGauwin, Olivier-
dc.contributor.authorReynier, Pierre-Alain-
dc.date.accessioned2012-02-24T07:45:38Z-
dc.date.available2012-02-24T07:45:38Z-
dc.date.issued2011-
dc.identifier.citationSupratik, Chakraborty; Amit, Kumar (Ed.). IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,p. 312-324-
dc.identifier.isbn978-3-939897-34-7-
dc.identifier.issn1868-8969-
dc.identifier.urihttp://hdl.handle.net/1942/13187-
dc.description.abstractWe consider the problem of evaluating in streaming (i.e. in a single left-to-right pass) a nested word transduction with a limited amount of memory. A transduction T is said to be height bounded memory (HBM) if it can be evaluated with a memory that depends only on the size of T and on the height of the input word. We show that it is decidable in coNPTime for a nested word transduction defined by a visibly pushdown transducer (VPT), if it is HBM. In this case, the required amount of memory may depend exponentially on the height of the word. We exhibit a sufficient, decidable condition for a VPT to be evaluated with a memory that depends quadratically on the height of the word. This condition defines a class of transductions that strictly contains all determinizable VPTs.-
dc.description.sponsorshipPartially supported by the ESF project GASICS, by the FNRS, by the ANR project ECSPER (JC09-472677), by the PAI program Moves funded by the Federal Belgian Government and by the FET project FOX (FP7-ICT-233599).-
dc.language.isoen-
dc.publisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik-
dc.relation.ispartofseriesLIPICS-
dc.rightsEmmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, and Frédéric Servais; licensed under Creative Commons License NC-ND-
dc.subject.otherformal language; XML; automata-
dc.titleStreamability of Nested Word Transductions-
dc.typeProceedings Paper-
local.bibliographicCitation.authorsSupratik, Chakraborty-
local.bibliographicCitation.authorsAmit, Kumar-
local.bibliographicCitation.conferencedate12-14 December 2011-
local.bibliographicCitation.conferencenameIARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, (FSTTCS 2011)-
local.bibliographicCitation.conferenceplaceMumbai, India-
dc.identifier.epage324-
dc.identifier.spage312-
local.bibliographicCitation.jcatC1-
dc.relation.references1 R. Alur and L. D’Antoni. Streaming tree transducers. CoRR, abs/1104.2599, 2011. 2 R. Alur and P. Madhusudan. Adding nesting structure to words. JACM, 56(3):16:1–16:43, 2009. 3 Z. Bar-Yossef, M. Fontoura, and V. Josifovski. Buffering in query evaluation over XML streams. In PODS, pages 216–227. ACM-Press, 2005. 4 V. Bárány, C. Löding, and O. Serre. Regularity problems for visibly pushdown languages. In STACS, pages 420–431, 2006. 5 D. Barbosa, L. Mignet, and P. Veltri. Studying the XML web: Gathering statistics from an xml sample. World Wide Web, 8:413–438, 2005. 6 A. Bauer, M. Leucker, and C. Schallhart. Runtime verification for LTL and TLTL. ACM TOSEM, 20, 2011. 7 M. Benedikt and A. Jeffrey. Efficient and expressive tree filters. In FSTTCS, volume 4855 of LNCS, pages 461–472. Springer Verlag, 2007. 8 M. Caralp, P.-A. Reynier, and J.-M. Talbot. A polynomial procedure for trimming visibly pushdown automata. Technical Report hal-00606778, HAL, CNRS, France, 2011. 9 C. Choffrut. Une Caractérisation des Fonctions Séquentielles et des Fonctions SousSéquentielles en tant que Relations Rationnelles. Theor. Comput. Sci., 5(3):325–337, 1977. 10 E. Filiot, O. Gauwin, P.-A. Reynier, and F. Servais. Streamability of Nested Word Transductions. Technical Report inria-00566409, HAL, CNRS, France, 2011. 11 E. Filiot, J.-F. Raskin, P.-A. Reynier, F. Servais, and J.-M. Talbot. Properties of visibly pushdown transducers. In MFCS, volume 6281 of LNCS, pages 355–367. Springer, 2010. 12 O. Gauwin, J. Niehren, and S. Tison. Earliest query answering for deterministic nested word automata. In FCT, volume 5699 of LNCS, pages 121–132. Springer, 2009. 13 M. Grohe, C. Koch, and N. Schweikardt. Tight lower bounds for query processing on streaming and external memory data. Theor. Comput. Sci., 380:199–217, July 2007. 14 T. Harju, O. H. Ibarra, J. Karhumaki, and A. Salomaa. Some decision problems concerning semilinearity and commutation. JCSS, 65, 2002 15 C. Konrad and F. Magniez. Validating XML documents in the streaming model with external memory. Technical Report 1012.3311, arXiv, 2010. 16 V. Kumar, P. Madhusudan, and M. Viswanathan. Visibly pushdown automata for streaming XML. In WWW, pages 1053–1062. ACM-Press, 2007. 17 O. Kupferman and M. Y. Vardi. Model checking of safety properties. Formal Methods in System Design, 19(3):291–314, 2001. 18 P. Madhusudan and M. Viswanathan. Query automata for nested words. In MFCS, volume 5734 of LNCS, pages 561–573. Springer Berlin / Heidelberg, 2009. 19 L. Segoufin and C. Sirangelo. Constant-memory validation of streaming XML documents against DTDs. In ICDT, pages 299–313, 2007. 20 A. Weber and R. Klemm. Economy of description for single-valued transducers. Inf. Comput., 118(2):327–340, 1995.-
local.type.refereedRefereed-
local.type.specifiedProceedings Paper-
local.relation.ispartofseriesnr13-
dc.bibliographicCitation.oldjcatC2-
dc.identifier.doi10.4230/LIPIcs.FSTTCS.2011.312-
local.bibliographicCitation.btitleIARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011-
item.accessRightsOpen Access-
item.contributorSERVAIS, Frederic-
item.contributorFiliot, Emmanuel-
item.contributorGauwin, Olivier-
item.contributorReynier, Pierre-Alain-
item.fullcitationSERVAIS, Frederic; Filiot, Emmanuel; Gauwin, Olivier & Reynier, Pierre-Alain (2011) Streamability of Nested Word Transductions. In: Supratik, Chakraborty; Amit, Kumar (Ed.). IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,p. 312-324.-
item.fulltextWith Fulltext-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
streamability of nested word transductions.pdfPublished version590.28 kBAdobe PDFView/Open
Show simple item record

SCOPUSTM   
Citations

12
checked on Sep 3, 2020

WEB OF SCIENCETM
Citations

11
checked on Sep 29, 2024

Page view(s)

20
checked on Sep 7, 2022

Download(s)

4
checked on Sep 7, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.