Structural recursion as a query language on lists and ordered trees

DOI10.1007/s00224-008-9110-5zbMath1192.68219OpenAlexW1985257126MaRDI QIDQ2272218

Lawrence V. Saxton, Stijn Vansummeren, Dirk Van Gucht, Edward L. Robertson

Publication date: 6 August 2009

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-008-9110-5

zbMATH Keywords

XMLdatabaseprimitive recursionstructural recursioncomplex objects

Mathematics Subject Classification ID

Database theory (68P15) Data structures (68P05)

Uses Software

• XQuery
• XPath
• UnQL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The expressiveness of a family of finite set languages
• Principles of programming with complex objects and collection types
• Algebraic and calculus query languages for recursively typed complex objects
• Computable queries for relational data bases
• A new recursion-theoretic characterization of the polytime functions
• Light linear logic
• Sequences, datalog, and transducers
• Hereditarily-finite sets, data bases and polynomial-time computability
• Query languages for bags and aggregate functions
• Bounded fixpoints for complex objects
• An algebra for pomsets.
• Static prediction of heap space usage for first-order functional programs
• Semantics of linear/modal lambda calculus
• Simplifications of the recursion scheme