Publication details for Professor Iain StewartChauhan, S.R. & Stewart, I.A. (1999). On the power of built-in relations in certain classes of program schemes. Information Processing Letters 69(2): 77-82.
- Publication type: Journal Article
- ISSN/ISBN: 0020-0190
- DOI: 10.1016/S0020-0190(98)00196-3
- Keywords: Computational complexity. Descriptive complexity. Finite model theory. Program schemes.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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.