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|
|Record Created:||29 Jun 2009 15:20|
|Last Modified:||09 Nov 2011 15:51|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Look up in GoogleScholar | Find in a UK Library|