Chauhan, S. R. and Stewart, I. A. (1999) 'On the power of built-in relations in certain classes of program schemes.', Information processing letters., 69 (2). pp. 77-82.
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.
|Keywords:||Computational complexity, Descriptive complexity, Finite model theory, Program schemes.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (103Kb)
|Publisher Web site:||http://dx.doi.org/10.1016/S0020-0190(98)00196-3|
|Date accepted:||No date available|
|Date deposited:||01 July 2009|
|Date of first online publication:||January 1999|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|