Premium
Characterizing NC with tier 0 pointers
Author(s) -
Oitavem Isabel
Publication year - 2004
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200310070
Subject(s) - recursion (computer science) , scheme (mathematics) , term (time) , substitution (logic) , computer science , mathematics , tree (set theory) , programming language , algebra over a field , combinatorics , pure mathematics , mathematical analysis , physics , quantum mechanics
A two‐sorted term system characterizing NC implicitly is described. The term system is defined over the tree algebra , 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. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)