On the power of built-in relations in certain classes of program schemes
(1999)
Journal Article
Chauhan, S., & Stewart, I. (1999). On the power of built-in relations in certain classes of program schemes. Information Processing Letters, 69(2), 77-82. https://doi.org/10.1016/s0020-0190%2898%2900196-3
We completely classify the relative expressibilities of the program schemes of NPS augmented with the built-in relations: linear order; addition; multiplication; and BIT. We employ pebble games allied with some number theory.