CharacterizingNCwith tier 0 pointers
Isabel Oitavem · Mathematical logic quarterly · 2003
Abstract A two‐sorted term system characterizingNCimplicitly is described. The term system is defined over the tree algebra 𝕋, the free algebra generated by0,1and ∗︁, and the recursion scheme uses pointers over tier 0. This differs from previous characterizations ofNC, where tier 1 pointers were used or full parameter substitution over tier 0 was allowed. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)