Indiana University Bloomington

Luddy School of Informatics, Computing, and Engineering

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
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: