Streaming tree automata

DOI10.1016/J.IPL.2008.08.002zbMath1191.68241OpenAlexW1995755344MaRDI QIDQ975511

Joachim Niehren, Olivier Gauwin, Yves Roos

Publication date: 9 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.08.002

zbMATH Keywords

query languagestree automatastreamingXML databases

Mathematics Subject Classification ID

Database theory (68P15) Formal languages and automata (68Q45)

Related Items (13)

Which XML schemas are streaming bounded repairable? ⋮ Descriptional Complexity of Input-Driven Pushdown Automata ⋮ Query Automata for Nested Words ⋮ State complexity of operations on input-driven pushdown automata ⋮ Unnamed Item ⋮ Descriptional complexity of unambiguous input-driven pushdown automata ⋮ Queries on XML streams with bounded delay and concurrency ⋮ Limitations of lower bound methods for deterministic nested word automata ⋮ Operational state complexity of nested word automata ⋮ Streamable Fragments of Forward XPath ⋮ State Complexity of Nested Word Automata ⋮ Bounded Delay and Concurrency for Earliest Query Answering ⋮ Efficient inclusion checking for deterministic tree automata and XML schemas

Uses Software

• XPath

Cites Work

• Unnamed Item
• Regular expressions into finite automata
• Visibly pushdown languages
• Tree-walking automata do not recognize all regular languages
• Expressive Power of Pebble Automata
• Database Theory - ICDT 2005
• Marrying Words and Trees
• Translations on a context free grammar
• Rewriting Techniques and Applications

This page was built for publication: Streaming tree automata