Technical Report TR621:
Edward L. Robertson, Lawrence V. Saxton, and Dirk Van Gucht
Polynomial-Time Query Languages for Untyped Lists
(Dec 2005), 16 pages
We present a language for querying list-based complex objects. These objects are constructible with untyped nodes and hence permit arbitrary-depth sublists. The language is shown to express precisely the polynomial-time generic functions. The language controls complexity by carefully restricting the replication of values and limiting the form and nesting of recursion.
- Available as: