Streamability of nested word transductions

MaRDI QIDQ5376652zbMATH OpenFDO

Authors Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, Frédéric Servais

Publication date 17 May 2019

Full work available at URL https://arxiv.org/abs/1707.00527

zbMATH Keywords

nested wordsonline algorithmsstreamingvisibly pushdown transducers

Mathematics Subject Classification ID

Data structures (68P05) Formal languages and automata (68Q45)

Recommendations

• Streamability of nested word transductions
• Visibly pushdown transducers with well-nested outputs
• Visibly pushdown transducers with well-nested outputs
• Expressiveness of visibly pushdown transducers

Cites work

• A regularity test for pushdown machines
• Adding nesting structure to words
• Determinization of transducers over finite and infinite words.
• Earliest Query Answering for Deterministic Nested Word Automata
• Economy of description for single-valued transducers
• Efficient and Expressive Tree Filters
• Elements of automata theory. Translated from the French by Reuben Thomas
• From two-way to one-way finite state transducers
• scientific article; zbMATH DE number 7003194 (Why is no real title available?)
• Model checking of safety properties
• MSO definable string transductions and two-way finite-state transducers
• On the memory requirements of XPath evaluation over XML streams
• Query Automata for Nested Words
• Reasoning about online algorithms with weighted automata
• Regularity Problems for Visibly Pushdown Languages
• Sliding window algorithms for regular languages
• Sliding windows over context-free languages
• Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
• Streamability of nested word transductions
• Streaming Property Testing of Visibly Pushdown Languages *
• Systems of word equations, polynomials and linear algebra: a new approach
• Tight lower bounds for query processing on streaming and external memory data
• Trimming visibly pushdown automata
• Two-way visibly pushdown automata and transducers
• Une caractérisation des fonctions séquentielles et des fonctions sous- séquentielles en tant que rélations rationnelles
• Validating XML documents in the streaming model with external memory
• Visibly pushdown transducers

Cited in

(2)

• Streamability of nested word transductions
• Nondeterministic Streaming String Transducers

Describes a project that uses

Uses Software

• XQuery

This page was built for publication: Streamability of nested word transductions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5376652)