Characterizing NC with tier 0 pointers

摘要

A two-sorted term system characterizing NC implicitly is described. The term system is defined over the tree algebra T, the free algebra generated by 0, 1 and *, and the recursion scheme uses pointers over tier 0. This differs from previous characterizations of NC, where tier 1 pointers were used or full parameter substitution over tier 0 was allowed.