Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/13187
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | SERVAIS, Frederic | - |
dc.contributor.author | Filiot, Emmanuel | - |
dc.contributor.author | Gauwin, Olivier | - |
dc.contributor.author | Reynier, Pierre-Alain | - |
dc.date.accessioned | 2012-02-24T07:45:38Z | - |
dc.date.available | 2012-02-24T07:45:38Z | - |
dc.date.issued | 2011 | - |
dc.identifier.citation | 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 | - |
dc.identifier.isbn | 978-3-939897-34-7 | - |
dc.identifier.issn | 1868-8969 | - |
dc.identifier.uri | http://hdl.handle.net/1942/13187 | - |
dc.description.abstract | We 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.sponsorship | Partially 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.iso | en | - |
dc.publisher | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | - |
dc.relation.ispartofseries | LIPICS | - |
dc.rights | Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, and Frédéric Servais; licensed under Creative Commons License NC-ND | - |
dc.subject.other | formal language; XML; automata | - |
dc.title | Streamability of Nested Word Transductions | - |
dc.type | Proceedings Paper | - |
local.bibliographicCitation.authors | Supratik, Chakraborty | - |
local.bibliographicCitation.authors | Amit, Kumar | - |
local.bibliographicCitation.conferencedate | 12-14 December 2011 | - |
local.bibliographicCitation.conferencename | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, (FSTTCS 2011) | - |
local.bibliographicCitation.conferenceplace | Mumbai, India | - |
dc.identifier.epage | 324 | - |
dc.identifier.spage | 312 | - |
local.bibliographicCitation.jcat | C1 | - |
dc.relation.references | 1 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.refereed | Refereed | - |
local.type.specified | Proceedings Paper | - |
local.relation.ispartofseriesnr | 13 | - |
dc.bibliographicCitation.oldjcat | C2 | - |
dc.identifier.doi | 10.4230/LIPIcs.FSTTCS.2011.312 | - |
local.bibliographicCitation.btitle | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011 | - |
item.accessRights | Open Access | - |
item.contributor | SERVAIS, Frederic | - |
item.contributor | Filiot, Emmanuel | - |
item.contributor | Gauwin, Olivier | - |
item.contributor | Reynier, Pierre-Alain | - |
item.fullcitation | SERVAIS, 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.fulltext | With Fulltext | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
streamability of nested word transductions.pdf | Published version | 590.28 kB | Adobe PDF | View/Open |
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.