Rudimentary Predicates and Relative Computation
Celia Wrathall · SIAM Journal on Computing · 1978
A class of languages RUD derived from the class of rudimentary relations is studied. Two characterizations of RUD are established, one using linear-time relative computation and the other using language-theoretic operations. Also, some connections between RUD and classes of languages defined by resource-bounded Turing machines are given.