Technical Report TR621:
Polynomial-Time Query Languages for Untyped Lists
Edward L. Robertson, Lawrence V. Saxton, and Dirk Van Gucht
(Dec 2005), 16 pages pages
- Abstract:
-
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:
-
